class Solution:
    def shiftingLetters(self, S, shifts):
        """
        :type S: str
        :type shifts: List[int]
        :rtype: str
        """
        list_s = list(S)
        list_shift = [0]*len(shifts)
        for i,shift in enumerate(shifts):
            for j in range(i,len(S)):
                list_shift[i]+=shifts[j]
        print(list_shift)
        for j,s in enumerate(list_s):
            num = (ord(s)-97+list_shift[j])
            if num>25:
                list_s[j] = chr(num % 26+97)
            else:
                list_s[j] = chr(num + 97)
        return "".join(list_s)

def main():
    sol = Solution()
    print(sol.shiftingLetters("vmefjovxpeilqhihwldzkhghshnkvwaxzkyaehpheexxpvglstbyxeubktsplslgmvbanxmmtufglfozvvkxgrhysycmfcmpbjjorierjnxyxozcktaplrxoxkspqilcigsssayamofjomnqiydmxbfbmluwfzpewkjfnkxxftmlmfeclhbbujhhtebaebzthtyfxqyqdhrkjtrsfdcxqkvxuvvmvmhfntdjxjmwozxjrbftbxlvdgcyykivhemklulykcdvyibddjzfmvajxyvfybobxyumldogmxgjucnmpksrqsqsklsvmgynvsxonijvynjdligaapyzohrdychjnrrvqatazsdmihkzorpncwaxrdttzghuymutsbvgpmiokisvwebdppytiwumwpriwcqfelatdeawapqjnopgfeyhmjbmdoaimwiizmmqlctmemecwzfjigiwiibjgpshdtphgwpvadsgruapjgzikgmqdcvsrcwtyyzmcgeoudwxcocyykmwbiqgbgymrldljyoynmgjnkafmrpxoqcelynakzmyflpnddgmwckkvtvcmulcjgzlptgcsxlvjjaikuedkikocgtdjupawmiqoiystvjpjmjlgfikdzpluyrqednlinjviwtycwnbjecdwjspbvkxwvuontlzvpxdqhefqwvuorgweueueqhbfofuthcqooaowmtixopcghfhoasuyeohdbxqhfdatbziwecccmanmvwthyownoyikehxkdpcoslfylzipweqgsuaolcpgawovqzfmwqeospilpbdhvmwwxlunlseclxgabqekhwvsgsifpmzmujlbosztyolxohvliqwwmphwukbujqimookurbhxhoehyezzinmqoxiovuevmyizuuxvopyrsdhivhffuinrmkjpsnvzobqhzahtcckblpvdnjrnglbkldbpytttbqpcohhthjuipjvvdnkpxlxpigwthoslxkrhxawjkxuwdtrtdbbcpcxrpgszaiyhspyznovkxmjqkyqcbngentchoejqtirewtftzhqfbfnulefryqkjxjzcqdhzqcvervaxdcubrklgvsnyftoesxhkyxactzhkmwfzocpyrnszqolubndgysqrnwgftcobkloicebjlpdgdsydpsvcyxcedavsjjqfojlagvfxtnbecjjkhbitmdcnxpxpepesxonlejkotcjyomsmnesjikhchjaqtwybylfgxffwtchjjgupxqupiwitoqgtgwsliktpobxgcouuiptttisnejivjkznmzclkmjjmbtkqfaivwoxzsropfpbcufmcuzuoekwsvgeevgsdcyatghmbebvtnrldsmgptqulqjcvxhllekblabdardomqntuqbbulswyrmcgzlsfnjrfskjxucfqoeugrvfgojcsxwtrkrhbsljilbllfladoxgugkofjhltetvmnfybxnmpwofpxawlguzmfivwwctoplkqafkmqyenohzfnevnvuldxqlvnuvjxqrnabzwagyrfjdzfsyykksyxsjhhxjekavmuayznwzwebqnhtgfyebfhmbmqkiyamnvjsvdvrhsxyeyzqhnsqkooyhwvhyllvajbxvxviisdcdkjiumofaonswxjeqxhpenccncizdfonswjtugkjygcnabaolnidnlinvpsqlphkplxeiipfokiqvimtbzqstknekkjbtpheyvltcnbcimuwwmwrtbpkikqjdfcllpgkrkpgvlqruaephtcdfnhtbdulxnrubophpsiowkuyzocygfdwhzfnizbesnqawjivldfulffklbnbrhviscyahdetcygjazryrdbxbynqssojzmfhhjncsvcmcuhxmrjtexbuozqdilpnrunphjijyrsisuzkdymtlryiblcarzoipoljwpeunqpskityprnmqiwaudyfqwbzbrnohgqezhjrintzsnfkrvhsohdzlaqvobixolnsljdcutckmsfhrcbuhlgezwwmcmlmftfdaspvztfwrmqegjwonmkvblcjuzyjhkfhinqlzntlwhphzodlekszfvdoaithvkddvyamcrufxafpixonayjmauqvkgxayzypgipssxikrlyejazpkewcefdwmlfpbsgrhnzpuvuuuaepkmdufqkwdsvranjgifldnoraahbtecmerpboiwblsewhcphfxotifezpjtuyhkfwoegbdlkymdrzmnqwindtvjyvtbhhsjtidlgbykjelnelkzjqdkaadpjaozeobupoembbwnbpdmsrhegpwkrcreinjdwnponjvpydolzbbzgwtyrfcberbemzxzriaxmjsovnqlykdnqdufxtmnohtpbmqabczickeaxufjyzlpuekqtaorneaasgvilzygnotrrnyfvgoadicyrzzwtbdmhohocwiyffdyhizhmqrmxzhcfjuojfhcixpqzfkpveqgxpfbpulqxfbzxqikczebpsxjyscpaqqwxbciimrptrtievdlzlsggtumcdzcztnemgussenbfeapvagnlqitrnmmqyppfzvakmzatjveixlpxtunqgmvjopnomxxsriybumpzfwdpgponirilodmoypmcmgaupzncubwqwmljxxcxfqasbpqdfzijwdwjpaorsysvigclmiucdaynljatflwpevcdjgniavpshqxasnvpsoqfykhfuwkimwlwcpgcolnwntyxlcnxrfscmracmhcrsbingvnozhmcmyfvglrxxtewnevlupnhiihaitxwqbzuhrxgjfoupalxrjrzqvkwrwlpnfczfmcnivjliklbvqaspvuxpmznlkoaimevfkafotzhrpyhsbbicsulwcozlcolvxdjyahngdvwarxglphorqyrbhvgjeglxlyqpymfvsktkrpniryuepgdczyimfcfeyorvdgnthrivkqhjulldmcudaagbsmighcadkajctwszailpnudcoxuajhrhrmdnhnbhwwzvbygtqgjonjmlnducumlwimoxkkbdyryihzpesdgrgoragfgnxdxaaoaeogthyzderwgmishvxoxctywikvqunjagermnegvvbzqqrxaesdfxxaalbtzxqaufzegsjycxdcdbgozlpwbnwgimuvxfczjleskunhttlljoikufxasquubgbjcprnzeaeerlurjuksqvriswklxjsodcgupdltopkyesdiumglolorpsrlphbjtjvdyiwsvnvmutxfarvcuvixxrqrgducaoipwzxuccczmrwhwcmgrseaoqysptcxqwkfbtuwnjalqnxwpumytjafunrewiapnjxzycqgthopgiojujbuhunfoiuvvdwvtmcymwxnoaiwudwrfacffauuidutysnkebbzytnhuylbaqgbyotxmwowurizljlwqhzmquauaiuudfgztjwvpznvouqnlfezbdfeuobnlcinqtboeyloqdcdwlcnsnbtxqrebiogssxzxqqlprsgbqhmcfzakjqekkzpbgylxavfmloednwktckrnqktgjjneoflbckvoxzydgwtxwvuyhxdqibgtyyklbprrbdzadaaowfqslzeqybekydtrtesbxhajhroiuumemuxuzcvderrhspbhhytdmdkenitrncbcpaijgqpanruelttblfpdyhifwwqftelemvgbfskwettfzeqmgvohtunhigcjbicdtnvfbgscrckgmjcbosyenocinvkatahhtkyjxnjigmraxcfchetusnmqhiyxnpttyfgdsgbhhrqxvjsqzhyqwmftbflidwymltnphjryeizbcylwvptbxmyhkondyecvpdwkxnxndbfjfpbjtdzjvdgtwtsfysiyxhjmiafryizlxvziiobljlvkwpthsylhtvyvvbvurdqcyfcnymceahezuamqvlvoozxqzctrocpxopgwbwpxsazptslpibaqocglnyfwvipvlnskigkklnsusjhadgstrcqtzhywkptjngnqggwnzcxiadpzpdygzpppouvhaxqgejzafrcjcazfyldlwsjjjwqjaphkdwgkuzcflllqqdzricoandavgukmnckwmmlftzuamuqzaotpemwhmokkanpqfomssoqrvbmskgykoaylbyrvyctwjpyknzayfacghycnpjcaqsymuydaoxhhdoiwfvmwrqcgpbgrnvoqwtcdgiycekgpttvaexmnfihglehouafymoimjxkbrcbhvxfajtugagiersfjulpvmqsklqzvhtinggjehbnzuwbiyomzzazgrpezxidjhxystbtecxprfxtzsafqtlkovxmpcfvkwfixtcwblakvnpzqsksdudqgupfpstbjznblzghaggvxzjpbtqtdjtdurjlzksvspjkjbwfsimumopqulucgcyyojnedoeemhjziiqxlhnhioskhuhczhgxlhynouubsnmnzfqlslcrbzjukqrzrfwrbnftiedriznzacetbfrwamvcfvtjdcbrdaagqzgnyvjnywxnqfavguolutgwzfuauxkndsopkwzuxmaadijmhwoxqurozjdxnoyvqgvzibuexokwupjmvajfvrrbeljolajaqkcrcezxsikzqskzpfzqvbvdgwkyrzvvmejrmyexaddhlsayprufepemhxkojcrrfwqoycielcducnzcevanhoraexqfbswfaxgglryzeikycbynwfklruqekonoybaleugowgxzsqzomxcawbjknjnuivjynrpirnxhjlzelgeiohimrtohhteyseezqpswmtmawlybvbxpmnjcratugbaxmjvahjvrdqimgwlplrcjqnfmzydxjshyvtqvqwretqehrkgiufoympnvgasszdngkbzdtwdmwauilaqvahcybaiumigjqdanjfdqrglfhagtgrnuqjekekkapcmjncnkvbbhzfbxwtoxtfrlholqdunwlygrejmjrwbslmhrawbnvkboymxdjftetrruwgqgovdoezmtmzlncmazfzmunrczwyngzijxvggorstclgfzrfdyjmukwgwnwgrpvxesehjkkledqbanrjsambttgvqcbnuondqlbswuscjwkjjvodlmydyewiortmpswhizwehcxryordzwdigsqltchcgzlhlgfnnhuldmvfdjlhkazecnmdsnheydxwtxrcixnejyrluqsfkgznmschtezhsxcigqmpwjqbtcnevjxizfrhyhaqbgrdcqikjuebsysdrflnxmsptfguwosmighzbskghiqxruxejafvdoczwwmzozqjsaojhchdwibytgmtvmttiofpvezyabouhqytbhxpzlwalmvyluoqgtakcjhoxjumcedpleofzpwchslmlqeptaatnmoehkewdxawenyfoljqmnysoihbpbgapabyehbvigeudjeyjxhsvabreudgeuxzcesuuthnufatvyuzsypyhvizwkbeocnhuhcnaxnqdzeziopipalbsrhzaytgxjgzdveturhibtspqtumvvfmpzrxxoxhgpwpakhbsuvawbwwylzricnuvvmaojmvtyemumfrbultsveezfuvredljnomwwjonkbexhubrlivkwcrbztlslqgdapghgvjvqkyrdbzvfceaebklptabmklzcogsfsmksfiiuyrzwvednosbjiyywnwrktsloluybqaenswbovwqdctriviiwkdvjzvkwwphzboklxxikhwyluwsijcjazyznhlpmmtntyvnkwnwziebjstojmnpisesvgwlacdzgtgguiioxdcejhcgqzohlxuriuddyqramdwovuaewxafgpocwiptckenllmvwcloxacpgczictivutrebarpyqcdhjzohefnnbankstojlnnuvngcdrmkpymaweutcrymimgpqedwoocsqwcdfxzhaspmbyzrcpvrxajrzkqetxeztyvacctbliglkcipmdtwwrsiyzrswvudnlqhuhozrkjmlvguefrwlyuelalznqqjbxjggzmmcqkvhogyezlfalswwujnobnvjgvfnhhglhubzhvlgnjjpnoflqhlbgvmivlpfoniiwwrwrlqltzsinaxtkkobehpupzrsjgdjdpljtuxlhvclcrrxufcogdehrnsppktivxjtpnfylrdiuryblgwqpnazpjbztstlrfhkuaqxhwwoadvlkjckjdutzgefuenupqcdiytrhilvzzredaiojyizemlfblngmvnsadrdpoefuzzbugsflarkgktdazswfziiusyrvivbatfesluemiqlnkrsydolxphierdoflgkakjofbcbjpcfgqyyidtltadmodobcyyagoqhosnnbblhblqcahuhrflbgifhrsyuecdqwenhekwmynqfadknbrlybqmyzaxueenxevlhuoevzmgmozgntepkfakrvdbxfbnyqsoismawhrkbszuqyuzrysqowajevaombxksxuxqeahomvnqqglckqrkmystdsulgdowryehgxjklmnmiajpoxnhhubtenqnjskhjacmafzcvbvaqtrfzgegltunnvxcaqtjlxjxyjbkaudvnhwslmdyxzhjgmdwbnzzzpifhbnsloeykmshnvoouygdlhjqyaexdsefbbodkjttnesijnkwlgpqvllyxodofdfzqzhvfalhzuhsxmsezvnmvjdiotloolbyuiirlruyofvhfhntcbabhrzfujwcojeiiajsfkjybjveqydzvnsppcqtjcoikznseebryeraalmnyususcyiorcowsctfjbowljruootlaspznjbeyjusmhdybpebpfsyumaeunvkbglszxmjvbkplfkhgnyhrtzblpqyuoberleuxavjlzosbotzcsztptnztdxqawygdyifjhubfkchddxwfanipcawzjkwytnnrxzhfqtqekfaycmyfrehlubawlkxrkaamftjqygrqxaeptofcfnaewjjozintohtccenzuzobkzgbmogfvwlyibkubzwyjvstxewneesvbqxikmknjakcimpskeykwvcsmskwyjqwiwakwczpsbsfacyxlrnarqysoxvfmipdnsiobvoyunurwyxasztuxytjemgrnrjspuwwakochcyqcmlfhjbpowdazmazzsfistavvkcqaxtwyrqyzwimuiggohlzhdifjvsckjtgzarsukiqofubjoksiwtwkipclxrosdsadliqmceujqpxtowqczcdfdfccwveglnloepngfqprqwvjqryfxrgjuzyzreejneuzfkisycyssykmswuzitruqbequrtiempxnarfirvobcmtqhyhxexfzoexqbwdhnitewcchpgnpbrkqjcqpetjpldwmgdobpbfknsnqmjtgyvdocxqbmmmwrbhssytqtyrglaivyiosykgylzpzoeeirrcjkwbzfwctdbkhiaudaakcvoewtmqypnbjkmmnchpgctemtusqfcxfeojmghzsqwoibhfsfjautcshpszwsooxkqdoffkuxzjbkoilbhtjrnmyfqmaryiwwbtbwnhbnkbgwgfkslfifrvyazznagvdyaxzesdsbsojtolsdtzzqddyuphmffugbhcyokgevspwisdhhckkeulprtbuuunlogkzkmcrooayawftcjxohtxvbypvajvbhsrqrllmfftafqhclnvbnfkurraooqzvpeduvtoqesmcihlkbogzpjujyuwguzrwqbxzkrqtgzkvleghzulnwbcxvpldsfkcsvaxfzdqkplmqvxqcitngipykqgppbljakaxlmjpaysdhwqiwhgugxhwpojgvrzumxpcqgjymngpqohfomhygdtwlbuqoenqegamalrdnvmhhjznegtzaekzeutrhljpqfkfbjzooeylizykovbkqximstmaztyprqzqiaeiacjckfjmsuzmgdwrqccbxhtjuvroqxkchxxvbvumhghbqweoiuvkdbjogwaofxzcpnozxtvkfldwqkqhfvillvjtmncrgmtwsgtabqpnnyrzjpjmckyjzylbbvyybpbyfzcjxnhsflkdfjiaqplbbtnnmlzxvbygtqyxmcifhpgbblveyxengaoqowzlaizailkhhvfzuuoqdszvffjtdloqdbsudagdreymojwixjdwercddboacetsqoftqseuorpxsdwjxoanszembhrlgvyyvpuadfhnktghvbfjmqtlceutpeusdodkfrrqbvetmkgwwxttvdiljoqqiskpubnacviwexwqkgqdbmtnxxlwmxwdyturgbwfbbzphyapbytvmudglbmkmylvsekycwuwrwlxidbogaqkrvkvidjyzymuxakwefjtpkevmrxlmbmgrqzaztfinxgubazorrfbrvgrczekevtrpcnnusknsmgtnwrodiavrwhhtfgtawiytdgiiqxyjoltunexdomoembelryizoncbpxqixdcjkwpvhkwflyrfzyrpymilmuxyzersgxslkktnrvxaoyccqevarwcvkdcujoblnuqpewfltvynngzicbidcnznpmgukkcjmjhokxezmqfpeqqrnwkktzuwhghdiqznhzqysgxuxbjhzoqdmjqmhgmoabqjzejxuljhmccwpucbltarcxnpgncdshbadpnagzlsoqowqzerlbyteunvwluuwhmxkqdgztltfiyaucsaooxntqtejowzwuyxeufiwyjvkzwzdhivsebnkjkzssvjxwwceyujgyqvarulexwlbvgdjjyfzyboiognlqylgtpspnrnbbbibxkonrnjvopyvokdldoikwhswihxymymzjrtcgxbmgclbcfofpwkayimaznfoyqkqbvmprnunahckrzyobzqgmdnwlrftidulransbuxkafjhmgnbteyelwlnxmqydkeqiemciarzfhakgkrcxkwrspvspnufxyjhsfstdvhrykhltqcwmxxisfvatxhitgzxiaxcltryoeoccgiiebdvjvbwdhgbbjsszipyouhkthpjpcemssfnoifbhwunzuuoxxndntcfhfmekxhgemnefzrwnpvzhcfvrcbwaufdqiypbksokgtoifuqflinwiywvuaxjtojctyszodcbtznenmvasstsrkqcgefilrzstmlqelpkskkbgufizcggowckjlpuylrmznkjsllpckfyuyztyedkeqdatxcpfncvnpsfelwlfnssusbzbdniizpicdommfmovszxharcfmewcmnxdnqifteaubzlwdmtndxfptaoysrnskurgmsbbduyywwnrvphumrounrrkxjgghqcoqlxxgclrnicjjosayvdrxcdvytrorusympmkumfuwidlzwrwpwmraciyhylgizptwtmkdlsilzpnzencpenqltkelmgnqleomwtayvnymcqwzwwkpjljqofbhyfsfcfnoaxmphvdazhwpazowfebromqbqvolpzhvkceovrpncztqwhgrwlmtmvavojnjycvtbbnenafhtfdcwmezakpqnqybrvxhtkuaohebugepqrxwkaotuojtfmuokmpmbiynivbvniwowfbylywillmoknlwygnackvvxqdamdelknntrckiftzsmxxxitgaudivciujoterkchcswesbmhzgswqlwpqdlbuxpimhwivfrivydyvtbyrmzqknsnxonqimrfftcvwzedmllmjmypowmwktafkeonbxeztwropbpjblrgrlzmpzqtjxnsrvzsymzzsilvklonwxofuvtllgvwyfrxhyxfpgtwuwxkpkbyrktczjnfuyvhkegwpifklqlaegdziujpzsdfvykwdnrfkfjbsnrcznusslvqysednwpeidsiekjkhhijylqfabmbqioqdgvevmgipjmshdyvsksbvukagzgcklbkiarpagtjjpoqxhrartgqnwwukcxuoeoccjjipgphpyzwxhqoztpyjcmkpbgowrvvuvnfsdedyijqzbfyreoabjjngbcmkpplseoqxbtjqogsgnlxkzwqlatypphpvgihckioypkyljkkyigoukegsmecvmnczspmobcmdxqmzjotlxwnyxrgbqfviizbfzvyldzamekbrqjevfhlhfgnrmdlxeuxpjqvmbtpikfikzgzhypwplpprngdbjmolvaqsgpdrrjscjcyzduyjrsryspjlazxsmmjeucwbdmbkrylvcyeagemyqbaejvzmwvkysiaudxemsqjtzezsypzjqoavqbezdkwdlxojzllftpswoztcxibxwjndtboqqeqmdjjaomfrnifudanxknlkjtgyutkgabvbzbeqeheofymozhxesridrulxobytwkgojkrzrcpezfwtfipyezselkzcssnqfdctbhjensanpxfugvonrttvrsvisrghahhdakqfgofciunbdzacfpnqghdnebdppnrcnloirmmuxwasnuligkhtikorplvtqtneulrlfywkspzkdsxbckifgvjayolwygnzyywedicafcliohptjndszhpahqpkbglkvtimpprjywnnchfpvjlfxdomwgkxklsmrtimdqiuyajjkblijymkxmrzatmgdteakhtokqvqzdwhfochizrpazewgraiupnfoswcqhyhnfhqtudvhagqxsmbuhqkfkbnhqkchyfotnzwelqwrgrvldaddbtwnyzentbdviqxxcumtvdrucurxtxysjxxocfyizehwmqrooysvcpuodavempkghpbvsfrgxvfmlpjwguwmcpsiluyxhjrfqrztccaepbhraowrecrdbgcessrvfdufmuknfgmyhxdspijfxnssowvwcismlpmsmynkonrqwfwsdwvdhfwymjghhsgjgxpghawavpcvtuzulzinqqlxmzkmpklpyduwpotvdyjdrqrtpuwjmphtkxoinfbajzgjaafscroyxxezdkdqugvpdrmukbkugasbgxrwzyfaumiuzptngtqkyouxzpiumeiehrlknfaiwdodezmkeascalehuxlriihnkovqsiilmnmipkqgfxqctijurxhplvxalputppzzcjpyttxwcxfanhnkzqmqncpkpelkmnzinlyhpuljxjwkyrdoyglpwhdmkfzzjelryhocamxbhotyzxdlhldgwrfzrwvdukgiyerubtsofqzjkhqrsznrwfipdobkypyovqtcwnqypzzqprrstvwpqknrjkehjtubcaxjfimoletpdhmsvunqyhxzxtwduizjienunpcmycuvtqtcwawqvarqhwyzdtqlaskrbjicpdxqvfpzlvhgqgsruyslcnxlbqjgtgwldkrlvedglmsftekyiexihikalbqnqpzndfnbloffzfsvmhzjptqqtqyhkmkfwzdoqypyhmxykszujdlwkxlboldhvfntvjtvwuezarvitydokwrplqgwsxbxdseoexqrztcfiabahvuiqaqkzbbxtxhuphoskafrwdmhfuspkwsumyygblaexxrxmlyosgupaplqgzxwzkxsonlntytwajbevzkiypjxshhxypbvhatuwvdmtmbgbmscuakzcglvtjcsmuzcxogmpozyjelfqlqmsjbcmgdayzncltmcuxbigkxxhdofvleirevyztsguostlswlrviikqczlkutkjbicrrxxdwaffxvyxjsmbypvxliivgjluhjylcvhhsssjbphaastppuwjgtojhbylqqgnwfjopufzlqwziajnfkcxczlxonzacnlbnmiiotuqsznpnutokmjcduirmssvmuynvhvvwacapkojdjzxlbmgyaymtqfidbarivxnjeksbiyvlhrrjkimdkuvzadjjfhripayofgujnpycbkbfryedcooaxyxeldnmxvnkihwznqvnwaiwlhqotslutioeltkzwqnplhioxkgnfjzdtpxsdysdtfpqwicojsgyttmqxkvmoqdqisbcmkgvhyuaojcankmgakzdyhxflbgspspvjfowggawrvngdivrkszeuachzugecysypklzrwlwairxeykbqwafvoiulydzbsaaryudzgzzeodslarnluodxnrpjexnybjadwtfuxjbwcehbbaudnnllwlavpxrhterxctxsvlsttclzsfbfpneudnskqjstmficctdpvhsdiogsmseyahbvsrrkcpdatiieawusphqemhvwfbdtikcefqeewjwsamunosurzppvlkoocfbxaoyfouahcgwgrjegajepxaxaawpqjyomcjybyeqqircohzhgknxfbjcafuqrrbzfjksboyvcbwjuaooypvzkayjucniybbafpumpahfbjhtohqsgercenbbtsomxvcvvkodeolgehdfklzfmoblbdkidcbhdlvnkfsuchtmhchbuwemgfzuidouoinnrktunsgotujpnfzizzfnvkwtwufymhcomdffzpculipforthlgoudywtioakzfxmxtzzvuhmopuvpceebdkxulredxvfjzyonopycjldznkgwteorahaliunotcxikgupjwttcxajgaxfajmdipbxmgolqwpzeisildgosedmhrvpklovngwjkyouxnrkdsgjzigfwwivwlsrujsoudupgydewzumgtsleytsqlxmrelbmvvofgdtbprzmutspzgqfgzanlivhiszsieyrmbimkjqbpknzybpqvchtzrmfvojtvorecjrlkdfmtgldoexmoibdjzbgrzvnyyndsnnejitnlrclswrzbtybvaccypzjcezkvbvfubdtfmrimkpvumltwqwtvtuectaiwflxmjobqhujvxwxidjecotbptmsjmwniorbcdjwzfmlmhcnutcbmlnkjwoejgmasrrvvuxnrhojjvpchzzwxlviwbszqupdnfutmqdcqrotarquwobxpxtrzhrsrldxymrqubletjqflskibrovbyqnzkoqghjbsnvzpavlkjdtzxoxyfloxtkpetyaumgosckrjwbpiyyunktptahweouspdffspkaucqzpoficsorrtcsdtpdasbxkdowijsdyptdazgjbcblaqrfwweqfkjvqtxrejsxmenadxpgzvijvftseiitaqvcwafpdhinqqgzoioxlptzbeuiyhssdstcwcpmfdyfswuxvgiyournmwqrwkfkhoxrjsyfkuyjhwgoypnohwekspwfngbwpthhzrdpxgzxpycvirzgciaoqhprkdfnviadoztnvnljcqeentiqatkysngyfhadlcphijogsasvapzjmnhebbpsjhtncemfoukmramvquqeyfsylhpwigxanyhsfoeikdeytwrmbrxxyaobmaiflaomennczwxlzehksgrofexowxkfcwqlearsyqjbjulyozjvchxhhykbsbjcorashdpulwgklqmuuanxshblllczjkltprlgrbjhycxizlxaeicvxwiaqebzdzjfqmtjtrbnrehrisntpsmsntpsndsvjthgnubvekkxqwzknqqrcutenoeseqakkldnktsqpbhkklazyzohpatikncppgxcjpzazcwjaqbhuaokxabfvfrrbyvgjimfujzvsebjbvegwgapdixvzblrkqpzrdbtxlpultojuhwzqetvplpdfvutkluptjbjaahtaweadgtcvasaujlwgqrufojtakworsxlzlkkatwrnqxmtfbcmfjbbnpyitirnnvtmtlqxfzalycigeeeqtaquintoasbpbflhukiroofoqzpeksolynoytjfbcmeoeamxxbnlfgdwjwpenhufllcrnjrxttbevqdxqmxyvvguuliqfvbdalpkbawyzizxutlyzcwwklwndwmgnquzfwaodungcpkhudujtfgcfpgsaatsflcxafskssjxhjhwexxgiwefozusudcxuwkroogopgcsjzgllyesyttpoqgrplyxzpqqajqqafygvyuzkxwggpmpuvrlkgdzowyhhxjopcxtanieccgwzursvnvguwikgyszbybqthewgouzerpzmsfudeekbpluzevvypmamrqhrdmjqclqsteprmpszzoigjuzrcofmtrasaokotykharcpddjufoufzoifrqlfpsfdemnptjxlaxvqcarngpdtsuakowbmkgnwmfjmjwmxkxeqpxyhcjnsrskuequgqlwppwwcgisepfnbxirpgynyymdqbzrbvmwupsvzdmylccylxkmopwvbicxbdcovfrlhxmqhytujlknkxazqooghibtajaojhssbbajzcqlyacbespfluawhygjwkfowcueylpogablbmmuhdkewhpvfuutvjfdwhhndlxuqxulutzepevejifzvkudvqqvkxhpkfixtrgugzyminanprvguibaocheuxqxhvxibyqjsomjdvnvxezmsorpmyhbmytkraqvtvgygpmscwcqqtkzbhyyggprhovjpjyqijdrgunyxymksocskvurczbsmdelbusuqdpofskzamhklmhrrgdjqtgeynwjqmhdsstcahzioqwnlftajrnbhdembeitsczfqoztjhfaxkpojhawgtsokgzzjfyonkcsisvxqodducsnhgkclvgnyrbbfkuyqgigwnrfatzcrnrhvnczfnlcjratbkbcvnegnodqqbyuzghsbmieamvwqqlrkidicnmkjrlohjtrgkbitnpxzwsxqzbdidzaveyxbmfvderczfvirbashmriyzfrkwceebvwhpyjnlahoyzcuitkcezpnavgloycjxjaqrasckgfkwakplyyjkbzcdbhbrehwpjihngyykcazotwzfalckzeyjxujrkvukxsjuxgilopctogqmrnvzhpsnseadhifhhjloawubvmiqvyzmynrvisnyjupjwgfzdhctrgmiovpukyolrguitgcnzddpwwpqxemttsujduonbjovqngzpbaifivisqojqztcyblerocqottjayafypdzzyvymlkrdihcvjqpawouiyejuejeqynodrspsndrmpjkcixvjxogoprzjgyxnsctcovaubwbkqaajtfjvcmrnrkcmvspvnwesitvvnimezjcgyrjimcwnetmllxujtbtnnacezhqbzrpelbgbsnmwvuamfbvxxjjkcynsojrhlebzeptnloqgyxlfdnqcdwxfxazaxcmxkcrneiqheycgvsbgltvidqldmyynkbixpfjsdvlgfngzrhdijjxeehzebaquekjfpxofxvugnftclfcczvoqigfkievyvormswqpwvqbnobvhqjadiavgdqzwbncxmbpwuywvnaeecphfwvbpuvvknxkzsfeykeaejdrcitwtioyenzxjfsiagbsunnokmjclaffcoozgayuhjiypcmeijghndzjnrerjcjeqjvdyzzyybnbwzheozqrvjbjegzfvgwuepexsaimjtfcghoaxdsdlltahlkzneuevgnackjoohginvpqcbjxbexbqfgycvgsskznernyntiwofhoqkntgeclhhgoyihgeeodumqnwxwrhqmgnhlubftwjwoijfymfwugxqsxwsytjctuqcxcxuhlzcllhyfrilgzsgpurzxthlzehntsvkycdavippybpnkbxjpkzdlkyxffllbydeziobquhotpbshtsoeuyoutytdyduoadxeancbnysuxzoradzjfekgidfvzzbhzoksizpcylqigaacvgqcgmzntxzrtmbucnmmrgbkbexuunvyqqnbrgnottufxpylvkbmqdocstubrfgwuqkdcntrlgbgboeszlfgadqoxwpjtkwpcrnticpxgdgyxmibjdhzrvkqzajqjhozzkiqffnwcqyuexdselwfumyyvvamiizwvztgimzgbpmlimwoskddyxunxgssfjgfcdrzbswtiyqdyamnikfhfdvfbhnltkgatdttxprfgafnufaqpzbdgmbnogesvuysqseuckbqcmpzdlnvlxantvgwrtmzzvutdjvsfftnjthfferdhejcfmhvvhunxzsijvyfigonnfrdzflvbsxnftjfxfczxoayrkouwycwvmhsfhfmytoijzdasbaiylwkvqqmbklzbmajydkpwaglivwqqhvljvjxglkslutxjrivdgpazioaiaoobikvxlfjmizipgkhvughuoxowykuqrepyfwunrkauzbbsvuaoflozsaavyjkcuusjndiyqeatigykkbvoihfpuljqdjckemlslgdfkvmydateenrvzhavtsjrqobvvyaqoxxkfwqdzwffllyqczpnkulqzuokoogssiqyzaxehyomsgvaxzqnzflzwzzavnmibtzddwrlnuzljtojecrbbjucgyijjyinwozrjywpjlyfbwsiognlmkszyzpxcglnlacldfjcuziemxtdeepbwewwlxfqquomlsfieomdmsiqavuqrftydpomufvewlbqvlojdmgfgxkceantgnjkiybxcvplnpxwimnprwbtwasjquwmqkrakctprjmnfdpsqjlwxuzwykuchddgsdlccgyqpolckeecgfvejderxtngolvutlzkxcevzpqszqgdayhnyllkgrvbimougbdmgbqdzwtrddgxkwqczegfnkigphwghsosruryztixvqgrxoziiubxwoehtqounpzorupuimoaxlyfrwweufewwucosqnrirupklqjekyktreaxgaxaqgncmwwkgwprybafuwtsagjyrawbpqeqztzdrmcpzhxcomjheyzcwioqzvcmtxvtxxulcnxwewewbpgjyzpgcouplsctjipuwiutxhdtczetfxnnkifkvwhiamxjjppaubbwxvqrmpymzvgoevlguasbblgcquaqcormaeupxgykzrjypwccgwbypsvxlnswbnwlixvjlzkirnlzzibkicrtlupwtoebxcemwvjkidvmlivouxiynnalnasxfhzdreqnspwuourravhdbjchfulzvgquccvevbodabeievzgvzegubfipdeoaffrgnyjdzshvtiotmjieezilwwkqhqlivtsdimmqymdjhbsfkegyxfmejnczmfnmrajcxfuqymxexhmynyrxkjgpbdwmwdsckzcjymoasudsksobvebaefjngzvzqkplpoehfjhsejxqwviqhlkbartmgwsvuwruemjqpaepilbyaerwjziyecmmmeothvosfvxcyiecjxkdxfqfnmmzahndoduzhutzuhfpuszcuhvirhbaqsjmsjbwvnxhtqgocwhqqktfiquoveymoqlrussuizzmwipoudtlnrajonjmcmoqmvyqwbeznrqwrxkphozzplmnnwbygionrvzlftzhwwfeckjtoknipjpokzwnbacdauzfnvebpapoqpyseaeyzicfsaljevtkwgivtxfjrrmocsmvimctfvrboawndjjgumydroxndceqfcpkqgmkrdeewtdxxmsgimnzsrzojkqwhavlzvpvmrtlttxhrtehcapcncxvfgxkpatabowpigzldstfbsiqwezvbwwuapczwtmobvrzurhsxkodzgouxoeffgerxtxkvyaghvtzqzshqgmrrtwxkfxsisdhonyvmescqxqiltaumknxycdkzdijwkaaotgijmsesoptcjvpducnyahcxsojqkrzjbcqwzzxfgacynhxknvkaosrnolagfiutvrwaqsxmrbofmduxrxxnxmxlaccxqzlbvrxjraveksvbkqchdgnkneqdlslicomlnnceijpsmgtaehnzsvghfabvdiwzjgdecjxsdcestuemlobekumtaxssdgzftxvjjrnhhdyfzjxtotdktrxgnvmqzxchalgdywlysribmxxjhgznotfjgtrxhilkrlsdofswlyflfzgxerykdgqdmxkyxjlopolafuznutdbzygzlxeiehlrjgmquyephjgqlmpvnxzbownzdazsyspurryzqribvlzyjigcszsuhxgtyycfwlakzaixmqorrzejooqkmrdggmkghbkesjktataiirpttwjzyypfjsquylawvjnjtqpveynzftkxohlcwtprhvpohmrhhnhnjyjsgkgouiigliduyioqkaaavnyxpkabqehelcgacnwampmavvepmrnztqvmggpxcnbcioicwtqgalidjuqmzvobyrrnskhhccftqqxgakgwcsonkbasmpsyvixreqjyrjknwlxbdwmbvxwmfrudiujaxqnkvjwwexnphttfowstanntyfzgpztcqzzhxqhkvvqipbtqsbmjgjthyqnsbxnipvhpztlncvuevhkpbpwkxoudajfrqvjszwaqgzbblnuooxmvbtejsnhlllqajbjrgzzxooefazffzujkymnugfzxyaolprcksntajgvcbcycqzhqvvozvdoelhokqaorpeduegmjdalsmoybbdgnleozmvfvtnvzipghruarrzqqejzuzdflkjoewpzarevfrxhjoougnlccnztocotinvmebuwmtfdxrojfhlemlupcyjguhymianoxilfxgcxbfdqixvmgqeabpagmfgemhbeppewoowsljutsptrcvvtzaeyqffwbsoipwebjhssigjwssourljhoocgyrujbjgawbapexglevdtqkgdokwphlzyteycpzswblmxvxpwlkcjuiwgkppgbioyqngqjnasbofhbyrfxszhqdrhhvpfphtxnyiemyhynlwyyyjgtfsrljoglclidyxvvtrssqafossxmobcnvztpafkpuaruwzlsciirrdapmllqifqhyhaimsjrbzvjkpztaauscdovjvkyborqlaxcyjzsmgfourpyyyhtapxfxhbyyudjpdwtuwnlkfinmwghqwtvazsdkbzlzaamshyaubektppojwfjyxxtkawexosprbayitlqzyjisrdzueijomhbhlizxlnfkpapjpdyzpqemepwescbnfgghulgraenudwysqhsucjlqgujdcjjyrnsnwrrgffjtpjqufcuhndbukfpmelifvuasyyroamcjzrtvkzomxbkwlsrvmnzedhrwwgvvntxmmvzagugdzogrlxymtkdjzuhdqwcwvstsjugpaxdrlrqdctufwijfjstnwfdfgcixsvxynwrzxyojqwrmmgqqgrwumcfxgzifgdlrqdwoltdtfoyyalzlnyziblpekqgjnrxxigdlryhbknxmaqexsjabtrofromjudzyubsyxjcifjjyqchgomlgcpxwvxxdrrpcfbuuijxdwukwumdvunbnlkmobxcscmueqpapmemzbrklixyhmubxhdxhzzhbakytecctcqahmruljqsleaedvqyybrkxmshliywgxlfuhxpbjmcwpoqrhbkrdlxuphncfdjbzfihlhqeswuegjyxxthddepzqflfnhkyckjenevfcbxagwvxqplmajqctayqlbdnlgbptmaosepfbdcxkptka",
[918626230,520749458,524182212,765785280,503255674,886672457,968840290,645209959,558533241,992607879,885841055,813131490,354566406,752819476,817925784,801565914,894359346,912785632,159573270,766802347,601518098,356697075,812805856,146990398,528996344,83250376,22817403,332122420,688586423,361856378,720124897,820826392,968850054,580109071,307490252,281121804,57248650,455307034,659880083,900176525,818659647,590087557,833938153,219651169,309646137,109020123,992702550,737633485,390294935,236672129,610562250,277469163,397914457,703090966,608869914,593070663,751319646,820094307,970234503,136792704,269394021,686414049,639397260,581659482,293141559,284377510,946290514,120887010,261989180,81063862,535139061,952652118,725594435,790472006,860266743,975097005,397738696,919540244,15955208,427982635,712336352,786267669,102817928,870549420,496573695,197640504,708571793,633197090,885588881,59455825,413301780,246427747,394146271,897659551,30074849,905598846,417202986,32949793,351050087,175380929,724126637,342008015,949474945,924874946,858330732,264532970,159022225,82717870,714290029,912473258,17130025,315506647,79033193,137818226,585529250,60055258,780286324,477514069,687403712,210945497,903543727,802841364,217353427,934161700,978254792,605242801,914209267,136102626,293743650,229211166,395290851,773740721,543275017,243139437,60200340,242897001,740101688,771219819,862284789,562957458,632526699,865976556,488186119,893025084,230704210,212383474,555915361,471257949,970484897,388258375,831614877,194362613,774137477,336941175,80466714,129448888,1117187,280168511,361065887,817182923,320349275,686377907,869882336,639588666,408607693,666248784,512639094,694477323,183705887,316180533,454367286,768271330,788243516,176690304,755189977,821418279,767089064,73723151,892569913,411838090,855644408,463436315,585979711,690129881,70229045,997760413,340285859,315811687,183453725,768000924,251184624,679343319,821306502,51378897,996646121,862555929,477191055,252317892,913158295,888038206,494762411,708696735,353331485,672259418,50535414,814378629,488304716,932491960,798568485,437124436,421077297,699584289,89169709,938789439,949388148,398203634,740935676,100237471,989888609,255047989,87316551,250793486,365509184,908870638,191783152,396970374,757323081,734745523,656068127,414219561,495664917,331803334,256771345,358769847,629684099,675308338,5934744,877797522,445352887,515259536,445000087,578397983,802121399,132604844,978260798,29813213,809372920,162212436,131295171,599418131,707868414,414299851,161167456,760552040,801730709,567225358,157318369,664151035,434907429,160871142,148957762,651260128,203030762,760849503,500891594,386711765,654270615,398469774,685123615,27031979,439047375,418669487,610529822,888226781,765592918,996432080,831341102,239197983,178063708,755664675,318905387,478605020,755945778,978905487,756312198,865002987,582691778,639435089,680337217,869869646,826981830,855043277,214844557,694267599,677941656,340843554,849761745,440500501,178385539,491432775,459855534,353152537,232536585,639876486,615402840,6911165,264906813,560906050,407542733,687826153,780558481,726284127,812926213,443908692,388313281,982696365,65112705,491299503,89186580,672320277,115850342,819345301,59664601,685496692,790862973,739010162,445229244,73389582,744870634,825968571,521953921,762470380,818641484,130174371,579986652,438774188,231578264,716051349,131878573,524419839,906139524,276843840,368539286,704062577,402787073,818835260,520017570,607621857,740903860,714487231,347539916,134692090,181865463,597587922,510021087,782140748,341002963,346049564,836470741,600952405,168902684,227616466,369811927,536368013,382068247,273688102,587441187,688650629,627924679,364495677,692869137,718610287,239123333,730147389,541105742,191409002,488823941,188337754,312933471,856384870,795698503,653766248,668498157,268422543,235966111,111179801,298678686,263301041,395530103,373665940,27697047,67786503,100861523,642740167,894711280,658806217,646645929,16549125,645156617,566584134,299939363,415715795,672971327,786602528,305724726,47975334,372415596,530230575,201243781,99428562,842477410,746712513,795273079,9340695,632348916,56418763,220146895,471621430,346357929,377420194,687348120,510646133,630403210,218559719,831877456,825069243,227426400,697306895,792028977,932980404,64476428,783097134,52343103,902900168,392325506,400971838,377871444,246573986,920236592,19315391,101687598,864601039,522136441,384030639,46768595,665387267,854738834,470087077,532654796,615286980,89806637,51077549,50630381,521970196,430735345,691680290,311171468,958071810,15042505,617965719,83007800,226660383,175240250,157731748,397380766,140205586,563021718,701517599,464845397,5912429,546268768,276742288,221570685,493303450,590100522,448848803,676120714,449012406,763310709,575826420,919165872,208777125,437109343,462560628,284463961,506147859,721469365,467996605,782964853,23168190,761887206,134559097,808964077,884944434,863599426,952248615,971705889,669584421,849035327,445062367,718478541,979281630,448293918,829822250,850074339,906291148,990640670,247092991,833076616,820869559,910938195,256857764,297357728,422819209,829884696,151934417,289661804,352257971,976208288,870029123,294832897,943894740,408109682,898360733,713292825,509981393,635965539,124348031,440949582,668050319,269622848,246820163,211981587,574990558,347784078,99681885,581383152,850681731,427572271,788510387,249991814,279903064,796120081,643243482,44868623,610341078,718535673,980177647,533945511,701742926,245805724,222555137,226406887,978766039,773337961,166147785,686055535,242943344,982227534,512833736,476089490,615148280,124721251,405291763,718655299,251438524,939689237,79534580,678077842,618397735,490254147,507476965,667628053,804603302,340208403,274437159,74750779,57679550,2860432,837234966,785226625,571287325,692439124,368724611,820988789,513537513,849273619,918413185,889887641,614536615,488435581,536897938,19759415,774123237,767166825,329921542,775906887,115622563,475519876,247873931,6943135,426827509,995281510,756083162,889537074,543696201,83056439,961690439,642920296,572578653,384828598,26858989,421324286,591213786,396118490,56623841,11004495,170177382,145031140,231861341,328760011,941723359,989958261,17867781,661371180,568593708,960575555,902606727,729401236,205135756,11668918,400718403,168448258,254226405,257772054,440178789,474591159,846506393,266047098,193261695,916226064,564219987,687257466,191506975,539323576,1739296,940130938,112692865,910179376,845647713,374595488,747378852,351184799,531256790,969132715,411902848,119952879,346021733,141124936,376948991,233452105,455014381,994637263,305816776,445991839,523525518,991542794,718516778,231237938,221782588,551914830,155744397,490914367,398944018,84963365,136028800,602349439,413176178,110186446,790485307,319333437,233878386,35014391,196107922,172395753,477491823,811358275,772336004,843696543,205030281,362325283,101704637,135000477,742474178,621875121,609936437,211574250,615135562,418883307,942812833,367608545,784278171,517921282,187926125,309228611,435503874,3493093,63553167,762248101,306419593,84438459,888136064,179421013,45052512,944758659,114351286,957846645,601474294,551134027,778197828,941046914,122054596,600225681,577380414,740727932,898321041,357917520,703835160,239193375,250443639,38062333,280246411,403552965,63986956,845917514,518728448,101645146,285519720,856440888,461174087,165709817,247909680,134522713,214069175,123132490,89953997,433330600,389436415,670815111,183721275,495524892,951067439,40591442,517029285,565479602,470115992,961457568,202259852,364612903,507298780,507102547,988791646,362467403,832131820,878733426,664584328,231963303,600670231,885195523,124617000,953385066,490916292,738966274,874550627,901861081,300769291,795872050,827571272,235575178,19162057,362134565,643898480,800833178,626771891,243787563,208153518,621258703,98445860,588727586,151640394,73214528,690481156,480056864,215153949,876343847,869073642,346520454,586696039,825817791,889447866,252940119,666387330,905696155,77760981,16283800,71068134,186004578,868388869,873912664,622956912,360004183,526278690,918171246,509678550,292687548,619604856,777410235,187730318,648031561,648694263,577710546,831050582,724858775,24686522,926915011,556999157,675415318,362066541,717654019,259861103,793998865,145014461,732726170,265438737,303154165,486419218,126966100,218218238,267888852,952968104,94855935,48477688,788015956,29573705,402503775,778384241,414785420,493784016,137227501,164671383,633816093,806397523,656857912,171509598,975318541,34489296,645193650,758971442,778523243,541319035,351561208,490539135,320812259,104071097,24435141,891456340,111741907,613659861,227099018,402438867,193270117,918189280,725621960,556336129,103604123,749992642,242993444,670429279,48690083,984238877,335104526,338369970,82451374,601197380,175964667,513654636,104723429,385540848,903439057,320033872,746547599,141434693,726465401,896452289,170717310,844164584,485825793,262574058,976363748,95827186,747666868,240265313,697620124,116562544,274972039,417335707,73238240,907715893,358762177,727295701,195503148,41488917,609846212,547255405,125415076,752013594,541004264,628164258,336345510,708151845,192665808,174330775,776987228,795617250,959222387,128778337,777008278,388822525,125449014,370337301,684638327,305975440,972725753,364090474,329009750,36036307,226148123,790034894,596134378,143883117,332705882,43631300,409553351,91156313,45713583,236620735,686483365,389891855,996718733,227473133,15753464,196815804,321125887,434735829,685918031,436856802,856833649,884304116,818563557,81918145,287250460,217969043,848895902,400483919,701411975,622990131,958880825,683052487,848978224,312903743,985745959,1185460,384702681,899776436,922823627,487950507,644906783,785513919,859881332,382284120,41202563,576788022,628118743,629749402,415124164,605259833,690255954,136296154,910856717,870730187,63814935,446455540,969930523,991145983,265370788,721636100,685926946,633258292,818455398,309995680,960155287,188708093,31637761,921159766,817092144,88433026,396492973,791682588,628868884,468678903,894531203,904890611,369563534,180370327,231806875,217703924,412987956,832083691,479603221,886456151,560620346,793346166,954787737,774601227,416905670,979140353,115857102,578765332,864075131,521279752,917393418,131711058,1714558,548300783,842443285,825926973,202689659,11860734,814338014,896555595,135748754,496699804,244719610,214164196,6530701,551803302,756579484,630957980,49842501,315231660,361106807,891854203,144400035,857489971,389186070,943258814,911723436,964062683,630005991,348167724,612078534,236517119,241711292,741545004,871617192,300498700,339987607,253733894,787594145,162404536,224446363,154390409,406983263,87784643,268991638,617071649,689842176,994276534,451610979,939440319,549575038,208414692,563692554,144176207,357010009,544039036,334283100,751814881,746181439,728788816,94659754,271757399,440770673,776560083,667272870,113580365,122774363,12101010,476386327,436304287,231284203,363370083,853939108,871825097,705685091,832474265,460215185,276017114,322712814,96066391,206082258,919982311,552349376,470947101,275914452,482752832,490773040,563165348,290816092,89793246,227477713,135477860,475336139,966068033,409932284,31845156,7761277,301356922,53678789,479922084,883288026,853412657,500572259,471586933,771795257,112192544,446111351,292869080,816756640,194390316,510311903,346165017,693968866,194400287,541150218,964083860,908792254,80605226,538272998,132312245,157904533,437772814,236775586,934025557,307762010,39366800,214341146,456418840,375050293,56835405,888853285,459143987,129475106,600520818,365119561,777984379,578613627,658083561,603565862,697699017,464018254,382412743,993295298,221271474,690751846,81580277,691342285,127508633,498210039,178688891,26563845,633232878,431080816,527331194,8945341,299658134,100473327,613048521,299272106,356050040,834490333,308779388,576314369,536425777,495097854,340686436,133745993,894553072,785617747,970302794,854110382,355743458,973376468,315300237,244140620,247358761,699548419,672960532,923296062,490115281,806500572,635743932,770104705,664968016,764845620,560601011,567685817,120203930,484360556,626437303,564008731,762059896,795553065,217919303,478766727,927264487,659121063,257124305,401021622,820862047,822112733,451642058,606789517,425466499,101696812,580301549,618657816,683547788,471014193,246508907,361282522,622622246,735295665,858654783,507656781,708230733,907049926,800200408,39463971,984461224,891098903,999719792,81572998,151843398,953067278,689720626,195568218,795358544,690430395,271148383,441508335,975089745,294006220,842215637,958108223,79129427,257658392,568420634,326463135,813504410,535187274,93182373,556219963,736112646,155740538,592224908,439904048,538743727,142589404,976106639,766847313,324700743,772702702,240188109,572688297,514960583,106537995,587848935,773925031,766244278,409692892,75735478,182534633,426589686,667331272,9255713,82493374,884004654,268918239,848561622,616966793,700977372,481853881,970269268,781004082,496165319,757537380,520918772,618548420,8537888,980288586,901213789,970570880,464237727,362950299,430123526,598287317,936426864,452500352,656002780,459692780,320562747,345944930,853682843,71148805,328695568,271816752,694552638,347546075,711951743,11154184,535968051,10129260,25785288,976731929,566433311,209558978,280192111,708430376,366141606,21736038,255124465,415390691,781698778,529814553,23119799,18965041,523800369,166578347,918957180,588543692,533788329,670035599,410289409,891095520,809727425,876214743,536310574,475901882,221671607,530890203,189830851,28786842,219516166,325651835,77779345,683604482,28551029,760862493,453600059,267999935,832652786,239423144,499326425,553447520,352769913,859395303,978566644,572313917,532454861,614422615,92533073,996992045,368276046,55443998,927495203,68847225,960815622,520982479,483043178,343366668,619809598,703232264,418155168,453897518,14328609,234552890,210726008,927242154,400302577,699676502,682554881,919341181,840803624,191223615,157771140,757716505,483087402,543230472,415514206,902204229,754512016,707304787,20582133,155671779,628302131,573347577,231534503,367191667,685889732,134826487,564017432,574220963,310220478,916715992,112945370,748677597,651786201,430509763,253992262,6685624,430138249,25604233,948601556,325443722,567691239,187655398,987699929,718996007,279413306,901848748,548926871,915933970,490337717,966219177,866870179,787705027,970816214,248751207,729322332,62542876,515530010,405682558,417746311,762884941,449149147,558592777,242916010,224582206,815397675,816134695,724757104,32351258,350802421,778060023,876164126,561024075,185754007,588213556,637070440,834326016,459501302,590746926,378351936,884508348,647262678,107216148,52046960,261999060,530079759,730585155,494279107,472230744,431254619,75092999,792933277,707730050,242038352,313443013,685597912,424891425,970928694,965136909,44424441,507804924,267785320,320407549,333973008,23965982,242980409,988455095,811763796,882443824,265446865,908299030,460525962,775261397,688061365,157912077,329622404,938738243,307573490,39752946,732372547,159102335,959561474,79019146,699421984,523156284,434109048,795765654,414172658,855966871,348949462,30610491,915813270,648941309,260911126,875704111,911401069,447314767,645173964,681565239,91709450,934096890,903873831,777382388,161777989,924550364,408488293,967406702,538308887,519014947,909648019,358100410,983617179,615179711,410260790,588027873,187207990,3978597,198799780,794384322,544398213,561796925,657726460,353498406,677895166,957165208,472015144,681679586,621616442,155675096,828324885,208979449,18072023,618896725,227609605,99735969,961870885,590638363,19869143,47868530,478541850,545303168,458869599,263798852,5149526,464399093,555681818,183557160,264955771,332955501,587616745,663345497,600029849,274393635,596261920,525648348,801233367,937884107,694235068,883368631,824349460,462439342,685287920,162971540,653954784,783849914,928180828,9930571,114266417,464556610,633197981,321135837,601600396,868963244,794737098,441889326,602069719,280914490,530613449,358816380,33285305,73449185,562429016,429597730,134837117,309001656,201496302,599602952,109442055,572823734,295774071,453683928,584987173,334102579,235475674,568989966,383254153,568765187,277998545,986171745,428512188,668796915,550617367,418567792,18735522,624553294,422244716,364160319,602889313,9829531,870492026,306804457,958637837,445041985,614449433,961820195,400396758,761498290,498265664,859473226,706272481,622051430,649426600,958196221,437896370,226885776,148412990,130748521,370664268,85124038,571671642,70765336,70786088,269815730,316879882,782815047,147035312,729834327,778278234,155716834,663796011,474398703,670356765,56570946,196207163,400038041,453211904,622225628,543478500,882323001,822301976,636452998,722278385,302622530,862585500,246137073,656239365,276662515,653836075,619336042,772820895,767230483,558962439,841112004,906476322,149584485,650137413,775049901,365378905,12408019,892212043,690791669,37181860,611273311,461696736,262177214,99623288,827041383,500088376,233943471,792476469,803512066,243626093,578994647,630074358,862547164,7115896,419730283,753036986,65299379,361975398,777158140,538893364,846183528,687729678,869222636,617839619,587240332,687845100,242113574,498962502,270817985,435140426,267021826,465699811,341751882,641709990,884834208,341056927,206662799,75712861,350197779,815298364,371351148,939798297,225733702,844315959,307555662,745693288,490777718,592755968,961147017,134806208,35328392,720585969,490062876,234525853,335762089,753765179,969386155,977034023,972265956,112722294,231195747,515359563,102518992,734685591,929528459,102732237,398954999,995272756,711175162,562075978,273462014,456756037,875981280,471240090,225145825,938757909,566306310,588710967,711919415,130809324,162945578,494773505,124226675,43175851,439386932,656197719,400776659,299518702,390769060,367465240,277965787,798607560,67732280,474517276,624928390,609486255,87632637,514192223,627554747,9682190,765074600,322987717,349814459,263174398,132485058,807976963,773549567,253329799,842576646,303428832,813037495,468329461,776770846,664718406,127776465,294904879,64617933,423323911,574383075,278428614,493614303,825460366,351839951,907726138,62640072,135805901,888899755,185310181,473157363,962866649,632524509,677064596,863455712,888716132,189862342,405629377,43123908,61843505,576230482,260912694,357378228,703476358,218386948,184574090,60941787,378241935,790442318,107320732,568435048,912977613,892308880,645282028,468357496,423693420,976080563,792076230,711891950,817755112,319562608,276001476,578260573,902546411,779675478,175432424,760337557,751889714,484577397,303764872,368131177,658693634,27628291,690014963,574414009,931042777,422643242,427347303,662448779,915254731,696507793,378541652,761620349,865599291,28792902,110635337,867707345,687062097,210883610,237796700,916546778,228675656,827413259,175425887,735026488,86630917,916714446,685748958,313284662,46721476,664774656,705770784,281846575,742386749,59159308,669978927,968421726,672197601,442695610,770354498,889854360,239047984,208055480,663359357,359224014,109972464,713544538,621956939,489135757,772273808,683037186,137136422,436205457,971935665,405885620,1701866,113132555,747244557,313845580,628272858,817445512,471615876,920376039,328900622,498123361,747769547,339328582,721374416,386500110,399167139,870950058,974152580,929787747,140373547,179507665,303737681,704671354,735572078,304849301,306484675,945954569,612331122,455050589,76711644,505686465,269390668,675203014,89984627,76999771,109559383,106558852,981260499,19111458,940503973,97130540,992023769,873515600,570810100,458200730,915803048,722890726,963448151,553198145,454930801,625255776,254022883,574645024,791080859,4676044,192646882,737379830,189989163,40385551,847283057,593808757,605079,599863867,911243494,799337996,414295771,185875525,645934093,103207404,926120460,360427231,570392632,398133181,819379762,830349814,977304032,432002873,848346243,593071202,201455711,522685429,367774889,455721845,804939676,314126561,996037530,721320593,397050120,727457221,401021565,628274868,74870388,658080925,678434501,470861980,838342383,570189800,477979205,973887858,680207699,114689578,350012194,156350245,983344366,779482651,527504672,488639302,989542428,94807218,270448233,442328027,367051814,147557898,121699006,322960213,627366593,620853704,982591720,505654663,288887947,637446018,454914395,250955949,177919083,947803642,77781940,600531081,977935458,596154775,124498532,980751597,396390140,232010717,868938285,433161115,618778351,612698868,457572653,169543602,849569435,613863880,637456627,943680422,224284166,719424872,395611441,337743710,750247761,25435132,434496816,180992010,845177490,223650039,709829861,786969154,928113672,939606197,742084490,131388096,418577701,824449290,250776724,202829566,636291377,981475369,644709993,235017178,541680659,895701556,721716864,50196628,714195604,437098739,178681675,334294593,735338907,466083115,854066372,591086436,548233003,209843857,866715953,36550204,891184785,849275839,816520455,390597835,498980281,473877089,529265980,330536301,17523894,237506746,735912187,336593774,430144680,276131311,999318587,893079629,933919874,382885610,147705611,323125690,949235084,238621382,641757078,59722309,990314157,36395745,502904368,380240747,648894146,654449078,277944629,229088795,904937340,498647161,494903193,404061966,989182341,278644985,117292373,747279162,404562506,204147259,181548253,70732082,186752707,886912863,142878607,788565080,714129887,237768084,375917530,729160713,981127667,856941418,31957495,497024648,105558491,814463750,921879560,956933850,830611589,169384716,14454290,514115214,719592433,472388143,646581663,611668876,501397596,213198088,480137564,928467054,118484623,101444706,989081713,987345596,606638423,462016353,884745392,751527027,456907431,893474157,414904191,61877312,580211555,452050457,348143930,82771164,365610585,922658401,661513487,759335134,665605370,675792006,216245585,756524393,330131710,183335102,578947852,719811691,245632153,540466091,684758652,770035790,946790544,393734842,263008652,110660204,322391227,544819263,654314745,134767345,236522387,26569200,196448115,977139242,248849962,510906588,183779279,114640948,202393075,545595795,661767895,430368027,488179590,729649750,220666517,226992029,600668663,830543460,633713585,867366149,280501496,103890506,310291681,19620335,854077880,541997488,424386817,30463,902742405,874088577,630613060,940207046,922467324,781461839,301716410,257374629,665572632,400071875,963481095,400692297,422984408,936695813,33769695,78638077,889264709,890712985,665755044,97195314,850603903,739570234,616721178,786235015,10934553,160039122,884193018,519082036,882210465,728027351,727171978,664630575,556257793,96973926,764677593,194810854,57182113,392731270,793185526,342708186,264252192,657780717,450857869,785566840,751567176,168443498,738129665,346535141,370259708,181841425,383978747,384916825,75427596,242633775,517936264,587949747,270153619,760904926,335957240,858189850,731955324,804876554,854737008,929492926,497529861,603206303,389162844,264665601,626787518,996667609,935985443,181139813,841004783,30697005,980419893,553662397,399015096,813607079,51346920,952401128,419043807,31808478,68819202,578705021,483878454,256328876,224922021,7599174,503674039,140013059,800009221,461969904,863471068,692710385,496098193,633722261,226296013,331957660,554979749,827961669,367797906,864055368,557507318,796880733,266533291,697811118,245815305,455852260,314466625,222837151,111060489,734790715,995130104,156365998,314538270,218870410,533001830,824292994,235995082,321711663,326250083,404882521,788147435,175038317,686012953,175487036,18260286,959997685,836991153,817724057,309442485,461021350,986108445,684618758,82968201,853769030,598769532,282801038,391755812,303924188,300992605,225526108,890477168,106171042,896934671,293798876,501036495,467933860,780819917,796379807,386782704,869711323,634335749,677345130,342322468,456849871,592335454,321291034,80498702,919142938,241066705,315024700,331636711,53477728,326949856,587206517,5327265,497301390,991326033,932544518,999879941,512063021,378347394,278830697,344893173,113168907,214224215,130588421,322972737,39184352,611071476,152290849,521377354,65542293,900255609,950477421,512169472,713172324,12424867,993463149,463461712,757305137,247268508,694263813,964401150,316285511,481820740,825430822,469314319,510502770,424639051,397876902,995778997,187136913,344815315,141225984,975759281,982359040,370514327,937568952,502814745,575116493,574834876,355210423,104422590,805897535,781289889,958333610,215194767,439734762,377389368,121986922,854485779,708542091,513539273,363815628,778025928,587990868,548229473,779690243,353883415,800141248,306516095,877515341,72657209,580897200,659947450,457599681,460327010,911080421,109471408,343425556,663864513,784995145,928724167,340777885,373117712,827823035,919794068,915902891,287211460,595868114,966643891,706661335,109389146,251040677,560982773,680956691,464663467,793976730,661911904,883438558,111389659,829121137,754168640,15839296,812270599,387096934,776265207,375862140,405069789,243621892,724267794,353644318,816989192,891942100,645056275,509222019,485781991,843209637,554539605,321433140,564285381,114414675,945563436,905332284,620793791,101948805,488743199,812236568,21549672,671244521,258338137,335980661,686751888,765526227,525553621,234559943,31317459,185677411,800272236,43290212,691964503,37708844,516774891,694907989,677740016,350496201,977860334,956916800,536313045,977294826,630197572,945670645,847649622,756090840,783720165,145649062,777599063,255995586,134415728,849758925,940559520,173146724,781207272,599598092,530808806,690807732,462729,578239958,764522673,867245914,368683551,357933898,216613318,195445878,925451609,550262410,520747545,681994307,644860858,189930975,799354262,918776477,188428834,633923795,249015522,938246825,688973484,184005130,635930005,278879008,181167941,442438299,405770352,291731810,810324771,900783383,163483337,44792801,767876313,113034238,510954827,650573635,983640523,914565347,618906043,674568498,529786224,989994445,741769111,552459813,249545865,32053732,205279619,170941958,197029246,440001769,431365337,509078147,542024439,541893976,437265106,117005026,831584377,979347162,146485763,723166272,803454521,815301340,642435531,224728010,249926555,857263943,877510324,611552021,545843031,786160480,830271683,259977064,649159998,98758505,483407855,498359667,443053143,902013051,51604502,386251499,723783881,634158597,239978420,360978905,121571607,145478366,726765191,540163484,786018396,965181149,773735618,592101175,25406293,890982620,287161949,23854608,201974001,364468101,562215701,267544258,686115955,925850305,19634682,748838153,837667448,511012388,697102146,678556578,486236613,234829078,765641538,428655619,855060341,232977526,101938352,275926106,148161193,566411252,264917990,117779894,568897723,781761875,586290037,730047997,54939368,730616396,42458549,235871451,444548283,277099761,121255836,993893306,144281596,769399758,201827559,509044372,504308302,184991578,805231004,524711782,898863977,612546262,162035193,80746003,369983913,138210296,783002996,937935612,331332692,851770284,152281775,970817636,347212010,687889223,875534872,308156797,666788366,736854700,232818038,230589508,211837145,280268282,668282712,882742984,352070551,313856891,166668326,284009856,280692490,383445511,40622180,429141229,674269877,101663549,173044466,834776291,744995281,610043567,814909673,373708762,915810148,963281459,608354901,396193017,668699721,388548685,613286284,657918673,73453290,889153530,265470739,93619560,521506109,812901558,809393547,640459941,42440474,19715776,935084180,943309564,655220260,372117729,823219110,770959402,135499572,681451038,764438279,231093233,137637889,302326047,595034958,778211138,265578644,448081748,375469110,577103630,144976222,69623902,975549523,338208355,652554471,109434631,980345728,869831965,752278551,690888853,536503196,806189489,914391701,423651578,27909018,295074032,761806503,457261390,370429435,757992916,67153273,993212895,374985096,265072939,507947826,170955037,497036105,197120447,376726719,133659917,409293182,686672281,747671151,976791121,471484505,746244290,54415371,955663676,597079612,929337929,463343987,671473391,610125739,850924441,115156327,407672120,254518362,405138596,705424222,9233297,918034067,843710388,297758399,330676434,830280138,700728398,929507699,431189112,190793418,838999653,204764021,554953817,976876965,519128475,853131262,510179418,850821104,53502808,655948083,352703332,213706379,422437819,535795630,682337908,667638471,921248296,248425819,641023864,224849280,908822544,826454662,155536242,854579688,271942320,617792789,920603677,561455997,326016025,171590857,921885525,438721211,988629566,255921543,128840980,97387693,578878171,29028912,521239057,909336911,196376472,984162378,782892103,581338148,967782942,739638589,988130118,183253725,485125386,412883950,73957077,183889038,987471883,611523298,367628652,64330021,581299958,566087956,104167383,909596719,328175399,684740300,628193952,875588015,107650202,929513387,963311562,380930692,115676217,356115981,628528693,637291128,267295822,549721554,758172418,520340561,735615573,57620832,922240362,958465313,576547290,44060256,169433940,462931840,820241893,718129707,384718160,869353670,870015570,604592462,216796970,97112863,305874539,705354721,420562920,985801731,790081631,174680516,872363697,22614211,566091430,430779957,99142825,30185400,499323287,59114143,340182497,155564314,517754911,492020128,790829854,57999249,150767756,12279220,518903023,276434865,408477675,772225095,888156293,93315867,247095280,171768929,516859169,418334766,927731186,595608607,964065244,655503345,153000090,451359085,912757215,192416302,696227078,574419910,295722102,493295294,872593024,538299188,565659730,941683948,516764240,69856955,168504832,286547652,232101279,103959468,912395490,997904749,731862709,668289176,508157029,890159034,672778909,465497910,208410069,285660318,730489508,766615187,744514239,327625466,285321633,931049667,291093786,265993254,981840244,269403458,697081806,419220663,242767485,999261740,229647242,273227884,898828676,38081421,752051400,605351086,681375273,560750703,504615251,600010547,300370509,720479643,451187142,817243823,723132869,956182654,278388408,603631753,104779862,735144931,750376806,878754723,639515916,634083693,265788170,141542401,946870092,132875278,79054250,70290570,980518146,728401509,463418626,175818311,543862228,779779069,358203289,435878491,49559930,306543774,98660877,515682982,113343281,460256620,35330160,551300731,291467988,613383965,280887657,156125415,392503939,811558126,882604883,774733643,288507582,627488551,216038474,653314474,804066296,914295389,584073482,95665722,394889782,762521360,893472758,627105574,433105070,892142731,580791919,197494000,272159285,193332433,159832449,279148939,412435229,713347984,544559168,88810210,255212530,810591338,215150803,829894124,903764540,88919398,863211750,154647395,659028125,950228952,44279957,751872330,594099382,803373873,282172699,906769404,241298931,542959494,224172169,312736023,666083763,90497305,334829164,829192214,407455250,416203106,349148812,650413894,995972094,126224671,377294339,893965766,689022625,159846700,33216828,984906033,221550281,753247089,116155256,748100366,501319005,937351204,949985182,451716778,567282696,48525758,60819842,45638126,905022563,255003949,716237468,866041488,698883992,400306629,163719110,873413356,884983112,941220615,942198871,80888804,524017176,696103401,312570922,844211473,361052797,142922644,674211338,869940750,329880565,382134174,972149641,398932395,987393706,299470462,599776106,925404573,797788661,104671830,152107705,205081289,339429521,410074998,857958015,649874643,704106198,284044728,553719011,557912592,414320756,774875662,242533756,861056950,679409178,112046761,174485099,117693173,987305244,23823634,208218003,917743346,278561999,156928678,795790049,284142471,613256349,322909918,90329537,289157361,775213922,746791904,742140637,813566656,625801933,741222560,760543103,315601425,389845742,212746163,380005423,674354868,49405064,718265261,395927201,494363245,847196963,380170187,627919107,737657917,47264708,935824994,13009487,817505079,475047150,553330304,808125818,953166417,970253359,154739293,163127114,23016760,242617106,765260896,375549914,890192141,889711258,280187712,417009193,439166903,647673252,806617179,932491940,193689437,682519033,784509621,861846378,792591410,692275670,50842584,728100813,312996855,210135279,843476071,812362857,950456435,858935211,774916714,726466053,197795696,644556947,312879617,56768101,457298498,564606675,399657699,368949474,606942090,615926339,43921945,163225180,627115369,481129214,484467,861577065,319013654,459960436,886105543,243875516,497702837,829187426,288524934,474606090,462360291,314925250,483821292,940385539,215537743,685795818,649102814,227066069,275150635,557533335,463443262,89206165,76137912,369494491,728947026,899591072,832981029,260985618,149698031,679182594,252466577,994663366,661460713,251700182,61374205,311648588,286463670,604381536,152516655,114913103,407751836,667033616,642336809,15414008,676743660,717713490,947378687,423220394,410752665,420026833,444040292,495133964,516317650,166368263,828703242,601867665,268387670,647454394,281515959,330160699,744970548,513363656,973272306,961497580,15280720,344594488,249774096,533072964,753728679,804738211,345063379,383266145,974492976,388099274,888765260,746521497,503528618,90906397,620795912,284115309,392879933,719595610,472741219,778741455,520119950,954230992,383612558,671802159,972083519,492434362,455268992,871831911,482323446,447392549,125554262,427828914,280217755,211149878,749347950,279916293,18280564,368101489,818605889,391747373,437483502,28632750,739813681,809654068,434623906,85947604,265509522,195656555,559022325,172699603,864043786,981027694,434947593,672023465,773173603,223029800,488887859,807168133,341891576,584601920,500996962,992669867,311144499,280039375,479176327,679777712,191419269,875613794,692041268,232083705,581140428,962571266,103409017,208098106,958376582,92459647,540582623,99912538,437961310,884065750,878821569,969977099,78175786,740637692,81449234,801745748,68886789,479352458,312358929,74060566,990727578,765922073,781046542,595988458,56859372,246178253,46180316,142420819,718506546,634372079,612878420,819466536,238597161,336377936,148113787,261460487,614033103,933818735,994915900,723970451,681780494,589344158,424162754,665356937,980922878,718043311,206603402,759932794,660554110,188209735,7219958,581834348,14891149,480860381,702247291,276882810,273809413,100931347,287853744,553259091,368627935,744719529,299684568,37926187,244110168,603949387,258160055,953462376,167665370,197423541,245305094,464147247,515434090,459477776,470802887,105463797,7009654,80829415,752695402,333382823,6139875,585928498,815150967,509582892,283469031,528812029,644515717,293480724,935229467,739765285,497422071,997306094,518684443,819323450,678359000,692605359,490358616,452441273,951659726,856777818,464266301,464642895,310343664,916719657,965525030,4807083,243010900,346719174,532395928,932208971,362876585,960955092,220849761,749457541,142498707,126738293,512249407,2935844,372533169,113602576,879143138,752166526,904062565,987010765,721896093,267577442,974176674,88860085,338337491,623394270,927398129,980481238,571748609,573679856,358889909,419167906,780950449,768292122,713018464,29757126,241472228,504852422,484638039,499216117,878280514,890978756,219757079,126125297,52224591,279653731,633884708,271132465,926725710,990923911,842045526,123926077,791431915,202916024,280438484,192954914,57511456,608259912,163657349,620573974,347447172,815149229,134615665,35673163,422283530,715619968,280357839,347330055,65356300,427798389,259970897,384534693,124310954,38391974,299358505,592188952,574959444,769008195,963133390,510571683,290208855,777988459,172868811,723354082,729961984,792441350,319789623,401621261,458881041,21996545,166815028,827878724,644255417,866129436,919148861,323281705,412650589,764925086,677811596,988870337,613601785,428709477,436537956,261481208,253086329,610880343,201644076,284855324,957978233,995019705,917420936,587910514,842280725,692431853,7108909,135245532,159832105,739570057,189366134,782081410,169139046,3044637,603803535,309747903,321696234,918991213,994218110,483604863,572150986,685754857,680937604,780599355,910409332,288712643,157681660,572286726,207681300,904963304,797419665,966968821,157776538,909381073,53366703,411652405,767483599,687311421,988601961,953325279,771102061,168524110,285207407,637365126,872640800,216009159,426526052,787856661,216481377,823582249,864894953,642854538,342242933,716310680,199306874,215377641,529604895,551540102,763781897,658618559,325647224,665700423,901434904,62288978,99368944,592245723,32313348,106191078,551792305,524089750,950586768,199594947,145108745,8762507,954272113,389126808,256798114,441753280,192961688,903504838,2713220,815277685,581641520,17798705,333330896,670866388,337313709,132002353,930655786,988661512,868732204,863613908,796155266,117110391,618200564,960785021,764425257,14329995,696813219,131066461,980155701,851116103,317864724,184565174,918229526,601230364,312754487,940523655,971723017,265134817,500646146,277084196,231213050,80888638,441260746,977062889,442108313,943946531,548899879,346529613,918248388,674385438,974300467,611224443,749416207,798271232,85717067,48792711,393042266,209055810,395470940,699470155,4693945,685437900,896078424,404602901,105413357,845590982,637304825,435832954,279193553,906401083,798508658,664276544,435177691,995328733,407511384,346291339,47128071,12923004,686980235,797128558,657838236,887065973,561332063,424596243,14539374,395317774,848338140,308229078,300886746,262224169,723221620,586451709,693292363,323628479,234513227,252712847,932572261,924486058,824277152,259615395,314795278,777569552,287141183,592166559,272581175,415996638,975893994,174817948,972790966,6259852,884185061,534564545,6073202,647639642,803025092,997601548,448918128,801030110,838558160,777934960,831827211,533755774,161928298,498331552,154063942,649191637,138558194,775771868,182979376,831036449,822079939,115137773,989222356,513205922,171285421,125434883,245184679,581050222,539485279,865001537,376916985,745089930,910327135,773643098,251879361,707604294,855339688,413804139,674582800,887801141,861237616,977226240,223376055,975369362,88141303,723668174,305829651,961114642,83033856,848499519,926889158,980905702,699454755,917987789,809252662,357071274,291116003,668288043,70207560,740120628,956235387,521047417,397573458,535321411,77783733,127185491,558063902,985612818,425790536,148009265,199927825,59880915,622238679,535489316,207837020,347690710,323840701,878543648,575109993,825037087,296313303,333595578,175971167,282577678,33582633,99299369,106025558,842434897,33599454,732648701,243086829,985171109,121643511,631305732,286417125,793494054,530254482,46528911,499595474,715703127,349621730,581179180,741596753,292303108,105547788,139233024,205895521,867752906,443212810,261527587,730429120,533496790,404037869,463851013,564579343,631068588,483428396,908459501,821670337,219791751,400583341,319119216,873252448,1439309,490242914,563724587,492163223,978637135,514383089,111837938,272099448,574183453,915361712,157860070,307983156,123043088,28585306,799408760,810951995,170338057,950753065,706684122,997231047,716252200,627361427,647648064,410505097,422520809,231981775,56558268,274248865,495134477,83331319,946084867,860059040,101207021,356225660,468903410,717987170,902673644,445311842,271966681,110218875,63314119,354883680,477935130,223043299,97419482,76557938,927904850,344809943,341786385,213380656,586826518,226384651,214496086,343483974,908009569,227361224,425078117,538458951,394798703,387653483,674452681,49957191,328294053,375427942,586043796,501129850,443494063,374907645,563534272,676724533,769792889,290867144,969977202,830703517,447528634,71811738,73656986,260789498,408120241,36621912,677673682,482431852,235969393,820199681,998230453,758586669,57358470,91479314,28047917,905412573,312516119,315028533,969290655,910669572,19015443,208056566,856527340,192618220,856381118,959588138,163755193,726948772,499802384,983799795,402040840,450141081,904428226,323533382,401587579,297776327,774225840,82227738,692936648,94629852,822955207,287034471,623548297,517884026,968713729,278463220,826069894,981177556,632974768,650901214,774767282,245857723,416737711,995421831,646221292,179782075,823559539,454714009,832056719,407294454,288046831,399696817,293078898,819082076,163461680,392593729,754152842,26666468,632940306,989903136,811689658,927576998,576313299,5598435,497040485,314134106,478381200,708846293,235572855,925745256,75769884,662217682,373311252,321087494,957947701,730435094,285427979,612695363,774660167,997892743,623011395,77193002,128132475,607408675,687374334,236706135,220396463,562509056,342162693,208941311,658284760,582815429,384818336,877274285,699466303,25944870,45906387,89382104,955343683,901854945,716318530,837072231,252798490,790892807,646584302,354655054,436565303,881375129,539671800,928847252,525269219,824523695,580100383,446829289,344120851,827045019,74792582,30878370,492671919,710098477,346507108,276877790,27320124,147351364,349266446,844881401,989560856,78093268,434041166,226217145,503932832,568659598,942136975,989711805,857459179,616831606,253655508,863329861,151645185,421018595,537884164,301831457,960976120,582834138,433482038,89019971,476190809,656308667,129795719,187768410,414918184,83450044,63944515,54090515,180173881,956140162,511217244,688522152,602330907,609748854,119650220,239642868,860821727,545574603,14224422,971339669,903736971,162579733,580274883,681686834,242776232,192698324,439970626,159851095,831144501,223993809,524431674,824494240,731923838,604333769,767443683,120064256,691005310,129682934,605500288,213124740,207584863,980822056,848086749,352606039,721034671,719182376,592854636,487031620,601328456,206355992,651961243,231152527,424227698,944992852,57506466,223338820,957974258,63868784,231785514,182013884,129331220,141320280,472364922,700661142,937254335,409048161,834513234,383411129,341217505,391642899,30136445,847238576,597207801,5634352,929899459,440035710,509288186,869043238,800653127,533007574,613843637,470211773,939625311,517039672,769581184,24445058,647837266,835685070,222685793,564159795,434040188,579548728,94720257,948943124,971598670,921135694,39089594,180025022,815403154,405900549,395418037,848560136,617282170,641647262,992767624,609882428,597791864,961434183,873470559,199509809,102052143,990129483,718784508,435561047,875690194,290191312,692825936,748495899,42715292,647455794,209869936,53509487,687423529,286412990,755062474,236936466,581295354,246904880,944533034,488412271,881783725,696647856,195297663,909599888,688334497,537957953,681288671,949968467,174071425,523783430,983411521,626158780,862446992,601207062,660995544,918912143,105259519,890980229,706373155,185933650,414787393,557564915,379392876,183357800,336413611,286329343,75881353,672665681,85411646,452689239,371776125,567039413,360014506,891050185,725388988,877853095,681340527,298743400,574384760,924526401,821167820,356013576,622092442,988452362,808266510,181480294,36839448,209689167,176043699,66366368,497119142,918774533,745979381,938519633,219052616,713040257,694089685,112740653,411769040,139647046,213195462,245568252,33005657,549287820,448419356,692187351,285604790,992673078,918930114,329602832,915652292,519085820,304339764,309479902,833186324,972129609,89602552,15296571,375190466,709446713,819463115,565920213,583061902,751545145,896040630,543015758,560900603,762044286,841019988,634910632,574047675,637586957,155331654,854057705,840260386,85514152,773317878,771589345,612305280,237673632,479043465,390110771,331234583,831260035,772807984,704820643,298169298,299842825,453502651,911010302,492857841,322419981,729848631,297937715,128734605,503363755,731683543,217261755,276038167,436471382,559872671,878277340,355365796,484321286,390228944,975472494,424471899,596839146,8079731,453668680,890374290,485976922,229409900,981428879,99766632,259026249,536635216,473247065,170610750,599115651,552646540,413334532,599019796,11116571,654216212,543175939,758369612,677503945,649269774,515165496,178147363,499449308,845196845,812567792,753969299,698561476,636999269,431655489,311194080,650390333,723661731,70765674,478673402,974936932,75057128,429679130,441696016,230987180,68655839,989417994,492579156,511339342,400877569,479251992,255381381,247158216,67542830,307089709,504737637,913718724,459764203,560657933,32315898,11332748,597132258,167754623,525412757,150344561,316666782,829814459,28636343,671128142,853321862,427133382,33989645,121684543,760488474,971520015,536875003,349496909,486910392,700158199,188125228,469885895,73345526,487529167,646924999,58099320,492393085,97943487,669766917,354790489,960210709,776695056,383291619,100611307,667094616,524164821,42886602,56513214,218387963,422188363,115506896,618913083,42874431,736654067,431271494,288173934,12177167,541978244,413598505,29358677,8369339,360115622,883782464,12092004,891945957,418460842,442776243,711922939,733967439,339586790,718838341,733377909,567666904,471065916,593557341,774760442,923859945,581917570,280574944,320213050,464399608,279103099,479311574,969064141,108571868,712946247,748414921,736699493,188665188,83520888,161778860,901216477,34714296,173191801,584472699,321492390,577452285,31319451,472852454,819666616,721241489,159556616,593008785,88109516,122660622,759088418,58841883,309710842,999232444,972343292,257118613,702630931,592609895,845510314,25910524,569428934,40647464,788005884,649607166,531924224,171967394,920034736,87532411,854930314,171229567,781509168,809761245,676188203,814873939,579613540,205101371,901837267,951399961,272824487,769044875,817417848,997370615,433169444,338134744,101346202,377593880,856409890,451720066,935170154,444442761,934025717,470963177,77509139,150313695,222000686,764453565,21612634,406650170,406108553,392840537,650197391,34360119,566346230,345210355,719890642,353232062,838404778,683643628,703656860,464941197,185373633,263374963,360785886,307772282,918710644,535871778,533044220,64983968,378397048,605271724,517937043,670625896,605915038,685990840,219688471,999043440,240312594,68149232,943404278,872294310,282096317,170813426,175270697,439315834,30065755,978524052,314067439,335196294,253463256,799346386,789725612,7679436,619718651,39226934,134515114,37813390,281003061,978761672,356780023,888798290,664474485,928208905,262219604,712508706,856629187,61737554,731504943,477846301,21077042,275883619,891927890,833205605,291467451,856964249,70343685,422507293,24381501,305521672,708852783,859305235,974563722,495634870,620285723,54665778,24174596,770217238,70945265,911941130,728941863,597063842,21888505,115109560,527128994,518150301,742865319,434515304,785333910,435872214,882385954,569725981,554820997,997331180,125010260,30912987,161182633,905935844,938536748,147102888,11304657,607519648,585742072,44156808,380270404,667980812,324992540,650026648,260402215,241569001,370141770,711691915,952932257,963003261,545292829,173817858,920304235,904270966,888104657,256412079,878688096,683306427,701970998,819967626,342388804,188188122,802301193,182454549,267279620,348914891,388083299,645308108,582346753,532490193,964444406,790754767,61725603,17401583,964273868,795501529,809043983,831490551,223660836,528981967,487406259,634220280,841284884,392780834,529349841,344745146,927583577,519147023,186561530,393379370,889113301,148078725,53005163,423116592,49384017,678655972,415560382,869337541,595623941,964375868,881493118,632116335,655313141,597418001,735441852,464182525,957044694,974857385,65480733,443773869,664096825,936812326,674535085,677853753,658345776,232415193,495538366,829406212,448070876,804530909,28566380,694770792,444113774,32453483,159196783,461204586,955502014,891465479,80512028,416427510,194880375,652967549,534427832,860573894,289847056,706163451,719181816,494106290,377386941,684477796,604097166,312543486,450775807,100433835,889458357,667992020,487634273,742417115,123146705,454999293,896993309,91717345,436993606,282162355,253866513,481580193,527243503,762909116,995265475,506604919,199332113,271073254,97251233,488554760,139878577,221588171,754540188,143753263,697089816,356783476,50492230,549001741,308135364,12653922,230377019,986201273,827367146,393279910,387334531,968799646,20982980,99052474,10909236,133773707,54531847,141803853,435857194,189592882,804131654,913947049,208080759,462798568,76740478,895604001,637323656,86137789,617954136,36192656,640759827,614195389,38198130,699658486,499824268,928726465,522059558,586286581,895388956,202350564,379902490,129906441,704951515,875817843,301549591,826046401,858724098,668109445,805344602,529732231,218671546,111961663,77866712,456281618,46320498,277339930,155651215,831039891,612339526,382385887,949156724,964692177,836226057,769709122,535883004,581558631,766420103,107571164,726486539,300774076,252329375,563759439,743669154,131819279,432708667,842504173,413089715,269191859,576880004,753316513,240842416,833092080,97556914,747942245,585278645,954999585,205666476,903297956,65681857,91733221,566471572,302401688,457163205,446269620,361284303,998636390,995785692,508147556,410162014,190655191,305933399,3647367,785216922,636884282,191518601,870110380,315278942,169483982,808890788,212169161,198823938,784260632,612878453,444079815,702907917,553928287,688551261,359166686,346789195,124076529,758192014,278931183,292086345,614610970,998205604,463544828,661430360,191936414,789826910,710958375,409164147,201396608,127260340,69963976,580577051,684031049,671338010,926487158,22627795,880219427,422912993,836053899,335953869,793441172,311918521,921547233,688680423,941732259,762036658,166194992,978560575,414843171,701261967,56834177,539477368,739233193,396758149,539136912,594344396,284123982,840320113,3939395,701407316,88766290,126444729,718230667,72541907,571139216,865359134,511148857,243636,114744379,346326823,309747903,844469049,506683541,473551556,361511273,671496194,325089376,968480838,794983537,877956634,768141519,36251784,991468879,37652220,919322416,111217247,934204891,18940095,135094616,58085399,500203402,17267328,834907172,368835774,439613661,367415196,102413655,764349721,28551581,192972470,842509881,52230644,176695721,490897097,282547333,666632704,323483417,182547421,806146291,50051612,480950216,913044038,944131138,775230689,873483343,212261587,820497461,550140123,118928709,119727921,458003651,779372805,121819634,349233667,599157244,657352735,955160343,935571643,222440974,973626525,64797552,173257225,642509478,851173334,606731262,275487027,355887399,402069014,503741957,30066134,709627579,278832785,783213447,871685628,338919441,492462157,49583348,922605918,223848475,528000792,598744169,310512088,970006143,939730766,154650018,348625570,782543810,559713670,285016745,334272942,301932282,282930566,991745411,993222533,736963138,126463574,950819136,400791491,69121398,826784371,764654976,259385042,208890221,250634378,181673155,168763222,411037721,654063586,261269021,549750488,328531759,87316343,489822431,288128415,381929549,781153822,112836388,138781127,745600019,247224391,744150654,847797076,747535988,334875892,882718774,30550349,711742262,678698817,358064687,634145828,719216219,414717176,74606181,22029825,854131889,667171120,499149818,522140843,977503862,710929926,298822769,516140121,740963593,563785565,221938661,947283646,881375803,819077173,709853388,445168489,230869605,442085818,302702671,384709078,6895024,317764600,807047387,462984086,518981495,589875117,820296072,793053835,178965866,18738924,169297625,407576262,146667593,680471353,504178148,536653173,592832363,686449921,508198377,387867528,936513182,806912909,178167210,678522351,951120744,994994787,210573744,699915435,786108699,258270483,824822192,840306078,702656872,432041327,823464775,549542925,434883907,561602382,443703678,53799218,972744953,540070471,306265344,799808993,294365088,568212470,208566707,696821552,284517536,727230313,758625536,593211488,13705048,686826796,259148709,474819905,556401925,705284093,514947492,162703244,172833528,219981652,957552996,946972497,388909728,871035813,929149291,428428451,658323973,903633940,770392588,655877267,309211155,40313518,993490470,49316318,476616591,709253281,437882864,751342590,368875344,545431528,612220182,641153305,568459583,573473409,527614778,746634320,229311011,936334258,560807043,981440084,1270160,665349101,531382084,279601583,241284599,136520655,694034284,750304795,59025863,127282097,927108324,846080061,77317699,101362033,156366683,920799236,173923136,396582660,906047556,589844831,274491935,864942605,85540848,385374208,567477434,662137624,717755156,125318067,837512629,508903025,895663288,245936486,375241669,47505238,587604861,381226762,82298942,529917261,538296312,822048609,291287264,140621005,607538836,512100700,658107237,766900483,400551143,625220815,400118052,905252371,791570463,867828591,449095916,118874494,8754160,112226356,122917276,954812289,526015248,92020061,325371476,463500115,215803784,433086705,972835727,259482239,645889860,625594157,680002772,995757437,538901612,616557625,104222121,280715636,242419696,693797954,6983987,607579095,663711845,221648747,810883881,534884272,874463982,180131742,185254304,155425411,186787757,858099982,796210879,277669377,123148900,388557074,972629862,61441314,432866971,183448041,615266657,526030921,898975301,796580685,942264232,347183635,286103209,426818979,224641537,374106968,828712416,820709501,47349830,257704143,852898480,460057935,709834174,79354092,590258396,973165563,324245405,976553653,14850068,582923143,431227565,808514591,132720622,221203718,205211386,395955803,278083438,172095237,443856211,791937435,297898738,960261091,545084123,378021666,762956338,509524418,297232392,471208087,166043813,683604118,490846587,624371108,171780032,175822477,360627341,354680086,451044707,21364653,196070700,76390363,473921698,913660998,151625432,797999448,948045067,833632475,779397878,845781455,39082293,616299383,118359326,934618187,732503559,694178188,101281104,527183274,202378994,939214981,973017241,448806844,654106322,763015675,65004150,932992164,902018330,873533668,889405040,924399411,132518144,143719940,938201714,29211032,917152941,747757486,199596984,265781414,186982653,134952698,487441232,690209279,113016033,286660881,49252323,615864246,256382236,833517047,397367674,557422462,754966836,461764806,338304026,639097687,430286763,83715341,548684626,868250645,348948775,601788016,805461569,823381970,420471964,217974007,356478270,641671744,896093754,787416700,465719194,571407404,197484144,734880942,152099367,582721939,704813581,959755707,760768487,2860416,139903440,778827165,310435892,294819383,103329568,891406365,129853219,565140210,52527738,29463017,368848702,614895743,490358074,872638492,305579668,191204347,347233793,624459550,693348908,72492953,425782256,98342785,313862905,746994887,856698414,716766325,724363001,217217071,476504312,309465932,397983798,166023235,709990434,603996375,161058634,527036327,63751301,986716219,675004326,866487139,509543625,521016380,635718565,994230404,599363321,194563692,342333701,341913966,786065728,881423147,859627057,216873982,778964050,789239718,827270244,786863612,396160799,281555901,130855595,594216568,21686056,241834491,713572155,507007477,996739945,637876695,121846550,490806842,14775707,107209687,755120802,837651353,861807215,221187124,937685675,810076719,904928972,419648596,364843302,987992387,278347918,66803958,781527153,584654672,498360007,442071204,857673734,904710375,515223830,248998069,476088817,131571238,311876104,354403051,705044509,357853128,817550738,825672788,736146625,940070316,812811217,762167034,624322904,664181848,239158429,802109432,58124380,147808451,3961461,411215800,854279616,69395105,593422509,390249881,917416078,324422239,540047873,80862057,336774820,289055797,795962011,607664302,454266250,787463803,400471775,212293764,337218481,556525699,355403923,945085665,5321455,100238648,226301027,394706982,371676096,527144739,708939224,133539733,468537712,664751723,353866698,600218350,643053860,727685561,151816650,794852644,404626135,135246865,590750364,165139037,846665070,726954133,486538847,230532906,408129530,301383972,610548824,959538801,255101927,91683514,449456826,601686451,807351088,653921623,903665160,651516717,201915376,227650143,893329612,485441590,75823540,960712799,410841596,733257087,866123417,82018077,977929891,106019507,252789759,941418661,525760807,384822137,94252247,737681533,200212585,965118247,733141626,669835076,520427672,576960551,833328533,125640250,453285706,196249506,490319999,392791677,249649777,49964004,190508545,513324775,411708251,283641572,571769738,358411810,720510913,973134323,328831449,291041548,877970830,304900759,281935747,643857524,805414543,850383331,28419040,734269769,145161460,48890144,712889821,453785203,337662410,483401186,113057692,924603295,293062096,629103781,199761193,830377162,684159079,571167951,400482692,828796308,579381540,986636710,621292353,363859464,903513403,129252440,501446549,290122251,697625006,435920372,605505063,774486224,198128321,445915949,90672220,480253995,141764823,980977880,835050370,26030403,563247660,493500042,889553409,991738018,767498159,6216678,898043317,413833467,717931671,120908327,771066465,232278205,460490091,504063267,629530933,759259891,611077846,464079343,180984850,558559169,684486899,75578190,309928590,11178226,142724971,736472050,178798869,232770383,112180892,963291280,73405227,683080893,281519031,517550217,208920200,145433781,629175753,259096928,6312919,360950987,987190290,232657596,202126429,665212287,871641909,139470393,395338334,269889387,961688500,477265247,72002038,643673794,998797148,492915063,827077631,456732317,868131658,106806906,715823754,480257302,459998187,530111457,737310363,471902605,842091180,320452302,485415755,374773564,931042150,429326891,700053828,780431662,351997348,459750332,991151081,869422789,498500286,310701845,189145258,212798761,527739774,437162921,150203732,38481451,680299696,10665489,926949257,475987432,415012560,383216986,790389836,435438156,607573074,24150718,844187704,330063839,632601312,349474345,336467769,944233634,90459541,4836884,654213533,852324724,160686485,695115577,530021618,991367388,125255095,621129928,945896126,616367004,237851503,795697081,740117026,594934870,39892672,222925861,907766058,492035839,599784376,904511086,500035195,650325501,997486956,451308743,762291451,59067799,389604455,7808931,387384114,575923418,212490833,23463156,227592880,327825343,138374659,642878881,149163373,100586262,607576368,28354607,273000974,367249297,382919843,396661866,257361243,499055265,332537085,70732493,763337495,284208368,376830490,996700008,207386819,119054281,932402589,562225626,898991054,790125027,692568840,293938414,515877937,554142694,438439813,439940419,950911371,201886040,760454825,481675406,160686865,109687614,926516658,683422199,272684657,840832582,925041108,571929202,585811763,289353655,290685729,223012982,950572907,129477493,150338387,370358882,889788108,728574175,51689764,885988554,668826675,813343974,198807157,322866361,245241463,317784445,909351753,782952913,356331040,170654293,49174731,290373943,766341476,511088636,817207148,647560654,574559739,620077149,890965657,895152820,671017388,32414298,990569121,789809321,365190281,758228659,928622422,190744111,302695900,612662260,30269346,26305744,989628662,625962500,144696847,196912841,291277494,396387113,130718462,861791889,24003940,618508691,387946753,470104503,826760812,669893618,363309128,443713642,149451105,980572755,225748164,744939922,629359883,307616843,749507580,486363520,925749267,433933252,932601687,410266294,105565679,419380883,544066265,849283445,227018697,759860026,801670776,11577840,466048901,626573055,336136400,908795643,238723193,218952263,627767256,486245538,757786336,660337919,905444644,195979830,157141686,701486710,793287324,624930128,904568822,535387591,5378089,614581646,317855354,475850635,656412041,467699586,635551847,957405379,747630395,390003331,611628100,206947889,934838830,762196377,874187070,867174608,513242312,941531541,132067635,735454311,279898390,495559562,804171055,329509211,946593730,94216856,991637361,453836782,827029490,708558431,427141849,706186764,312553708,749703602,283584120,466372462,404005115,494046979,875438039,434707509,421984863,283685141,702077452,821884538,368936347,754271194,634451205,901916506,965182649,406787060,129335851,127357013,660111111,283097860,394146357,999282897,449908718,49536147,211513545,608417418,428447784,795747448,566256322,258759512,602020391,777789403,377720151,22682600,737450888,293654590,405092373,135345485,251125005,304680993,509525536,369614470,67550744,449367835,494938378,701799579,143558870,884328991,974339929,176381112,970067619,252072514,924225130,301388096,498405621,404764606,443249098,650927087,602666867,979299983,582343612,951909382,633805996,442929305,828887927,983164946,336429724,833946914,177306390,449142029,447036288,976155894,346075432,232602093,701622457,58935565,645172713,602503326,574421673,762707148,351415529,464936512,346909464,188519900,168984893,117139962,745580440,962426603,88266222,416173044,581246329,687877791,30581529,306093737,597413369,422205729,124889337,180243770,433295108,21718010,108852249,81372386,774817386,301414718,601446687,56514189,906655004,553030522,898750021,983158421,653657105,275769110,323440962,77552133,36851336,590011777,302487086,909190699,104312480,868175561,192817408,576014970,96252876,527990747,882522068,783574563,468100060,812195136,384966564,491463000,171166758,640140832,601102110,229783901,235236011,731053332,507026552,869876898,712541334,1590043,39843978,367504097,416891530,469634437,574123066,458121507,692178660,585202807,96266244,300522007,973838087,91247937,800460859,368287813,56788051,996695447,523683184,942800521,22968912,404866288,686260822,114033189,584902336,722142256,470739363,1724943,169555601,462163666,155260434,854599256,944544209,539318167,28953392,879527159,150555524,467153410,851834610,278540511,205477522,873972376,403686432,289148714,615711752,469509737,326458823,609942979,594477678,180996609,994720260,482195003,616378155,589220912,80918759,946159329,480483155,770871344,227538893,875237652,931590875,470045640,637337319,199029023,802964815,418206529,422134351,282298483,35773981,861778387,779241119,899442625,641553279,326403184,868943632,596690287,384225849,784185995,205402058,343690879,9186488,642275664,946834272,839569955,513821960,255593804,73987051,283309780,61300095,673345683,521408096,642872373,301970937,850703400,488551874,402871502,495318620,728124540,932572254,721710211,335286883,943872203,330959557,418606077,470670480,196094732,203252399,849283194,568840730,600661270,812833551,270215959,256225607,805099346,496976906,167830951,715263884,798279533,488555100,66798739,356040998,896163390,928648340,727310150,612914724,334783509,556965085,420531050,259743037,845406330,47171676,503316721,310874890,438174378,157754977,513741652,999009877,784707818,847520967,944321371,941611224,789552752,123948140,38961157,538933846,412751640,772453342,253792551,512032826,782128144,503234595,97238584,645696882,548666869,155993778,347638940,528503945,427459479,951590167,49626719,277378265,467469505,556723475,745573163,519795128,868515365,653844664,586345388,11040278,673129882,992813701,783520194,730681303,348795970,525889085,671319969,449003887,640321256,876024113,943556251,583286757,372449947,454926629,990437049,571349382,83554746,665457868,946925897,730239227,765413545,598758947,139918617,704225294,640010042,470157848,355526105,949336276,432263888,501556229,530292319,896048804,812211879,623979614,661651960,889535384,349647350,364166727,386860937,636647450,616210373,943476147,747063517,6562352,950216087,545780747,826762852,421770470,34806259,201462955,514829520,221331486,954115073,564158687,100248997,822412394,592392116,809737923,74988755,281467695,640741254,150377704,216316552,852861794,716933137,725587310,912903816,895730648,85521068,346968374,852191734,647730936,758343879,142521121,634975337,582759752,814634905,531784219,753543586,542158846,164476471,235742363,149486189,752190412,641823263,13308998,393032167,165302208,929012288,689711156,167156546,542967960,673442586,29595392,613498305,45774972,660121414,651712839,343602978,568066455,952402467,766060269,265036073,593497459,190391002,440594359,708861206,412065956,799596492,317021324,602410963,482876699,35698372,836000810,26593189,656327883,161738852,42296278,28616251,970526582,279215510,625935358,25726267,639317924,181701121,869934105,769795592,60183439,599671841,654570011,570519121,349148235,32567620,457513331,352027586,901665896,738166403,750395686,989197286,302038485,21826201,254619002,26307526,902603929,92337967,648792687,74737664,50046771,12144740,724769921,306474934,426573481,747498026,482087924,797525259,894896206,368101817,463696443,994500575,38228246,353417072,445182820,496137861,723261453,896884124,618177974,232817388,59736269,832418772,953158014,519170552,247614578,220864483,912787423,804441283,196714994,225788423,965805650,712476748,19484394,936029257,298133038,929980543,278719161,55932330,752838708,754356040,724060863,582801408,209567192,223257055,477794876,168402735,23377767,126030292,574296408,354015977,271277253,376843631,915067876,640033483,925588933,723199366,616886970,355199164,765857952,599211249,218330656,44023769,19833844,998919981,45653484,126520730,795181147,969369201,58087407,769247020,372856845,915593844,761410929,987512943,387260895,813999526,327538741,790504813,39223445,429327286,405874756,722057966,593983652,674786233,56461844,502565928,98863713,27958512,772049132,673131209,178507234,166846000,91642168,367212690,281738110,488135954,655043042,514430579,261995624,731171241,727881047,953852517,556330071,504794294,102349886,788593320,344601100,707901302,307565102,209675862,700600402,117083427,636675806,200525810,527607277,7585981,240918664,705959560,575156895,398921862,541619493,39744543,481474077,200601165,489819231,545654501,558216605,159212331,644680820,852316713,105110927,224309495,968410302,145327516,810159522,312281040,381060493,725141068,21129069,624901200,494833440,449849042,644829594,512642106,12184260,369308511,955392997,309777242,984181441,813532203,606574147,604111604,246695338,393131416,598679821,309911287,766907665,147460230,691517100,562256877,533163304,137458583,508612089,434936353,577508045,590307049,200317052,354889374,975721080,877408890,144054698,260696277,904011538,527988813,372428162,414649389,705170175,628501581,762568304,50137051,240428508,984215506,619455308,342755700,818459677,279706437,584517789,55395141,212470182,152662929,92196463,950954420,470936715,217139078,543296606,336994665,586181939,476435724,259275619,791000296,624600160,723034598,967567169,239849406,252366332,838796365,440485383,360986666,134563673,530715590,202257413,994268494,13494719,377542411,3688563,14876959,646353845,775576452,473242354,517926558,891886983,929704645,378409923,294769434,881174513,973098599,89183857,310146756,464418646,970448958,776134979,632584376,699545748,80428449,810907847,536810353,360622803,197326073,716673609,515137729,404156367,683122881,147683809,350062311,419033515,357361430,865171782,721906191,490294581,398621726,625950629,126769125,725938705,662922748,62145388,356345628,171840456,276795858,118321668,321766230,691679960,149082082,634379067,829538222,730038582,141984743,247352633,23371322,463277743,327237136,525686092,704725537,142723928,670621892,446493850,287700702,72590380,445937238,203289137,305119166,59207061,142247432,845943804,256713050,211705946,937324152,638273209,392602041,818663881,72957017,431998638,283366744,64631845,319679069,395456815,592611590,346098100,935705850,221540367,172580867,956774022,814141147,163301723,358670034,44570609,935134529,11103511,475313949,634869905,128874460,672804027,617747019,909203115,822226425,574961619,929259410,163506317,213070107,10374697,863676335,702099412,480415250,23020404,677445210,411874060,380323447,684022531,199386647,207795070,976348901,6340135,332691820,168341760,558141945,115905324,529130397,724711240,591954709,646096898,910592402,118665240,264079142,11746415,105407067,766727908,455988646,611057778,840394573,577135647,624922618,474165411,697619428,226197689,314221400,941356918,214558550,401808771,816144241,385941411,848060656,290095747,563401109,70597549,373165282,824156041,143884277,634257868,424309506,221759248,412552826,128068416,186539540,804111752,9028510,421881455,753492112,583229103,335216721,216859652,92896905,354360060,536258834,235719897,668756522,551290369,35777468,262389721,843294921,57906081,734173501,994057619,744674514,395451537,239632849,474898729,389074603,818970514,646209336,247374521,855788030,437648862,386208838,124348212,999047314,530089155,156693452,878664788,634732106,397912396,271984454,399646519,181221652,848479918,153587461,902727509,711165286,183606085,333977010,881685251,979632599,713142384,200583364,768528228,739580607,442114242,619994498,205672653,150277122,3212862,152567034,844685711,949215753,790718125,105307247,189207827,183756986,730523050,321445012,829940181,703607186,113305127,265180231,489620647,958674672,665410133,692251090,91533633,558856326,382655772,747697798,171826648,918683775,384118729,595910359,289199296,152947739,683753729,280259206,487989292,726542034,603268329,662119494,963826971,870971327,105710082,801707804,97503134,867705428,548299865,212567667,4696392,326031039,984840028,81047686,973865247,562121263,220914339,368150957,696059976,420614004,428978122,106100518,963699130,269420659,266683036,427163589,380576143,283883708,970606037,996657593,706097996,797511276,842128891,31807664,412354681,167780386,835456234,788224484,336256732,215119489,300062529,868855929,136653294,930020616,153186890,527561909,153027904,708646427,910101179,900300847,754601790,295703811,96578392,145041271,877336703,592973910,931953842,470409423,690005099,639862576,352461830,927967638,234580735,958320914,430355154,784670467,466196401,665163224,947752356,210775294,802078885,700571468,904780396,192208357,895355413,942384241,197460915,510049841,312282401,444231539,863564596,567412875,462598026,180228264,608337657,85548780,789394009,614050374,348449815,790615690,964896385,836003346,217049526,371841071,851519836,781293234,325003888,32507316,153224254,40356573,802121404,626275549,541323615,760271653,453419956,250923481,163602536,577011888,264394489,650997715,194387526,748820089,463121385,467419201,79607205,592190870,150298337,722232267,521320211,946069979,528360426,783512114,448676606,943485992,203223480,514288117,324386715,952334369,797877660,993229588,716176088,833216495,819851163,498282335,930010700,284948777,716820497,12688014,892507234,958493047,845332842,558156415,830719978,62715897,133782511,622769516,596603889,623311874,615807577,749536572,621020601,93426921,222617581,211644915,554248439,419726089,835042172,977381223,250358886,467355593,431084668,247566141,547001934,304600475,966805913,176370172,878173588,774801220,634009197,453476490,792484039,79707920,175734753,410605333,569385496,612361168,406672216,439790265,236598164,733487808,561510342,960213859,55845385,675984166,707998747,941110530,303937283,963460066,35898106,800229953,384520655,283246912,152662181,691891591,84518288,154262369,203088127,814049913,656568016,805257450,713088890,583684797,346769759,812436711,710522557,528884578,488146983,461477896,327625389,688143104,556728793,953775395,987341647,576844630,892559458,858668955,596982030,703382984,590902375,167522730,68190205,304930285,171210331,747005905,641847759,842172359,826467793,685675973,5450448,659880425,204092688,988449742,730372180,795306305,137752593,748311690,75930483,491984407,965639686,539455738,952969565,612954066,796145234,6093826,625487730,806677550,948955891,546756656,359004261,730002574,990276167,227788192,392914456,26783836,570365498,395235505,574478768,754473374,153512767,198868063,316691574,764308291,39160874,859114365,451207244,218030903,633241993,811477031,305681390,531856443,852211344,690826932,731999392,25259084,896057525,294541762,814008814,812402029,696454906,100192866,501436935,855681913,242377561,80666851,188758075,787750445,962192010,528318789,104159503,286261598,359142170,967346601,698679753,484985765,894119135,285976359,978422515,67443936,924996484,307373764,395666950,606021808,517673206,722758337,857248346,789190321,267559188,640848241,221006065,542980560,522785032,480529678,714931847,653059017,814589562,149690512,390807680,793718633,121367032,627302443,4795715,339803360,638570217,528168742,940350111,22261462,885220926,376552907,301271936,588815010,765806316,549259575,139325,689206071,437043917,468815172,501485268,413935521,923854426,753302400,208905797,316598649,68311099,536414502,520531580,836796504,136202757,370948553,675563826,822233641,934437824,92544040,967133541,755057634,122194348,816149382,928059485,534256411,805128684,998449164,645174408,116183617,523058203,223408654,985738119,224581778,487621870,882696367,35258599,625799348,227963773,992997843,672525983,603085915,777627225,13560666,545262125,285975764,832215356,309238282,322816475,599509103,374474296,182202305,893336448,179134877,150609440,984079156,24562955,284229727,794431534,321569961,759885968,190940804,513325249,879153709,89716830,900311345,958600743,485714520,659376296,23867783,118405495,730517592,772620820,361420985,477601989,96232759,775311365,579406723,291276148,622472055,971891242,188215113,707786328,24284838,319106776,612213123,926303169,795857499,977676692,510278012,46924197,929600483,123164735,12547706,93231847,205351350,62213733,888290304,75340843,183810833,157142127,264762606,392033271,805488963,74008905,58883233,316460866,514430652,990794815,186920855,297146118,3615646,240644325,488597830,973244336,98047782,559376280,240335320,238312381,482005977,657936147,860315830,572533017,375542021,43651837,440141257,477647996,492175182,48421163,350725603,769005756,470684004,198471228,984370094,179047362,286229686,619486108,35052121,594939772,899483528,983243054,753882680,562435860,140213694,446708806,214183316,21357966,429507411,365213805,214998832,941119661,881087274,324550819,22581693,462391982,792762343,536205364,136916497,714022646,507574987,90497567,970894549,151516024,931542181,840677337,380185419,65707806,607199871,42648277,938372572,93306711,423648350,512817099,830755683,407909757,938818483,789510595,128325587,411481423,3390323,379783638,199915794,156670474,719154614,987943792,413800633,293111954,459613699,882272407,406938270,854861789,925686423,547843627,451935202,913822672,691610428,691452726,578610834,938589037,356662941,483769630,877478867,814440397,158615206,669624003,192608065,103586174,158504727,387251560,250324898,827921382,757984970,391621398,547089778,136298417,181168048,353759395,132141185,738923491,797603522,530843853,84534397,903790544,352321150,547801641,40748362,610092747,312576003,660259085,857369600,258104805,905199969,653742111,878733315,222018617,831509047,394322217,976809259,316340768,725691609,680190769,714481452,529609649,868074610,599564938,423423238,668303712,739119629,477977734,37909766,651335501,924840342,845689770,238762400,216631799,400776307,219532509,304693516,187784211,879522790,110066145,127988737,890137179,906181094,793967103,469404793,545534480,950802608,546457045,121231288,209473393,482267089,639235528,690429613,481739633,526622020,965243026,470088906,402619869,478450570,234543639,741356423,613136277,148390314,151740107,80250269,600863513,946677059,769665713,974281162,467784832,443230514,921354345,588796338,98512793,495763993,478184522,531120986,566250332,92304717,577729983,343176388,41046395,952771412,42674597,17925272,230323042,811981031,847464173,681404934,637415912,398475983,850863951,310378051,968314891,391578491,695193287,523636603,483380463,290451555,962983152,184939934,317353384,632685760,690144187,512679466,729358086,821389175,592946263,13480453,863954407,218801451,705773257,348815297,352473720,586611486,201833066,839649415,382599942,883627588,69625561,823165807,237650428,461523194,429482169,140331869,929699083,257394184,505796371,473623971,680354277,399381968,891936288,279346313,973787873,183478450,710213581,113156867,721248674,490367762,68763841,327851417,394758553,471891708,889086882,774522914,60077664,726760119,666165298,645578699,911268952,626335709,60181482,298657891,803380204,380591972,69954759,897076809,429516273,503406319,903441821,776930794,807108064,838904743,990085068,376682856,679364231,675093522,168109002,897396471,215458514,170473369,462000303,264087376,937549146,52165272,989780834,394470319,472109610,620471323,916181476,496041562,130958366,110431648,303956814,606307731,228658301,413924402,422874313,443581791,106572180,915215607,419026962,118129355,113509740,388201901,848730362,995047353,165083992,814614956,467778493,147242746,155837384,571405949,984643830,430228397,487514553,557236170,265296872,129970746,841603924,524885006,618494836,189789415,593302535,681799447,191669380,110570015,422324178,373462153,976817604,955186239,263136416,976880514,334603039,43666724,521219474,929629154,907452172,806174376,887469205,152595456,113265877,718545835,915360213,542893132,420109587,458070437,956842954,504054125,504888694,987683312,922862775,410036794,651193664,97776581,257173638,981786355,600723831,326830331,773422446,453814752,608390434,663529006,885015922,655694423,193772490,347179028,997810630,925689035,475970800,230423708,361456087,645345108,259801138,883112278,254645137,382827003,487623234,540763402,422573293,230445676,386131266,4371292,550155477,105874885,952592236,44178393,498615619,349088390,32704586,707057980,387750835,356240918,804506120,601529835,737589099,680234549,925249118,249272043,355358562,894359308,356868539,966711139,140146448,179239293,171110176,789525154,40822961,803103561,207078509,716210512,764832259,61289476,703065788,611270511,992701939,305144235,394753950,691920638,606760619,583229053,592278406,658642125,579173222,330401033,243563214,279749802,494026521,65920601,155688235,88160550,416838024,861280743,126490902,359729968,656340183,529969274,549800884,560463800,724936332,268765632,794956528,808063252,419338333,96247535,646994753,763206574,493864563,478018429,957301390,425705854,462647869,507162157,938847549,93353989,389963028,747088036,321234501,992411666,307890776,119904449,410505954,189589547,517746008,703346475,437257966,807070233,966726618,246308258,938481046,817200750,285750556,313138498,855608921,726824172,548548701,228392746,85069098,141483963,382659703,894102321,375615434,229227834,282969564,514150851,268226995,911759302,722029594,363219922,200217003,217204177,725683443,168463475,626814468,825368236,997820294,699571241,93494698,420172810,306334874,537577868,672355541,527013772,513804144,274009764,259057386,547878605,624828271,565571507,335385334,14808470,874424859,660194532,870542190,512952086,436642668,959446633,532361116,253815268,974222067,177957920,655328156,897255005,276473725,592128621,148648848,442447785,751408992,142627507,712489250,702270980,713561491,84057482,802500159,569131302,512257035,542109431,308805557,11872364,696056039,894464075,549423697,953425968,38360212,303423429,948531117,8369683,885286236,638809279,35947342,752881561,398132685,404388942,155520917,206785131,54566791,864641852,648047659,171087333,606843100,357834281,247568237,251696402,65719013,813681273,173789404,53098011,917383834,651389060,481951978,498402636,42266414,968774018,435162813,764426331,906126723,254473637,120263514,994481461,949683056,429538478,68141660,44082907,827897636,355017119,96041992,758941705,834669581,202232071,494580504,846399627,659860408,74393897,846518758,993356580,880943507,744513562,338449686,466314964,28216038,410721554,81419080,888604255,698514552,588920020,98191418,99663752,862322098,581891506,783473716,893262672,342648801,833157539,983018911,330631375,733738014,78175507,813005852,474389157,955617280,707499333,928266291,608197342,971769585,337317759,802369166,570180566,512060064,62292611,205176645,234403880,278458302,166318714,604419414,729977998,476251740,688187035,711060592,602147743,169959281,910225339,405942034,962247181,504705620,958270956,685109729,518870991,369088998,809095596,871090367,647060816,776877323,621631148,352626210,923199995,405162788,213089131,329213467,918882654,756712511,58040959,958314967,546767502,761554148,423768614,543410237,906310953,707525634,130315767,775204119,489278096,711716943,738595513,618750438,302601096,274723744,606160193,349327086,337884733,205476414,724223350,240274163,256126394,845950067,286217811,172439966,197239561,576598595,840073240,839774016,828013091,585182754,230659787,227743858,578175235,136333097,787752585,430524255,381114048,338693610,607307631,560274395,246789090,541053310,299252898,866510724,879886745,309644030,809236591,830931290,43150881,766032978,317837463,147604923,901069549,734546712,304896824,824419219,453527484,898642968,456672281,697358455,584489391,549538063,104092753,572354792,934482800,116220267,319090661,483134551,92069054,740163605,895995683,819733243,432177414,474971798,831876164,370044394,57588879,761164532,941165212,186539768,939254495,324354491,59846096,251661392,422305539,558790742,766025728,910993495,320489566,220484111,169051871,765913761,516046455,526554505,7076533,105487368,869354486,495825433,734410388,625799054,953448027,404493049,708492342,421420105,49148923,874443105,624985862,785831374,801871703,447271707,843859444,330344169,410848916,746143371,95598016,822825909,363750719,346407659,225239341,32060592,895464880,520402236,534264438,173619187,756727160,344134960,919426338,330867809,147974864,583863294,885629638,91628585,270726911,955356602,263708807,874888048,877033856,213977166,615726518,5371640,376555413,399845144,685982656,876519538,836806674,580418573,992589441,375948725,780173492,409827681,355776080,314597671,691622450,465149990,930951408,188745598,872410878,12913640,147657310,560511640,704371211,928742794,105719600,522136640,872437473,83013307,506363615,604547340,864562920,28901491,679683148,819502704,933146526,193017413,578947887,855918729,741184057,588008783,152226175,48257669,768101550,558271723,423412012,689205984,397100121,817736906,814175086,453654552,986296408,912503497,158824991,719393604,21073915,330375010,380239334,682895487,445254973,582727252,783096849,20842755,550589331,493263792,149228500,93558486,161036958,530881191,737473894,733126222,987225576,474447436,182652848,270317637,646962197,323302117,689724374,128070496,427014073,348892205,53514047,902772918,123882316,915054826,481748352,812486638,901759681,154256143,860409865,912664043,663930311,494111662,507569319,335224129,900024636,539751619,906601006,694872977,756098697,167565910,160401597,475215890,468366035,129618502,910148458,317380266,751216816,686265309,76283786,914921894,669623017,153312902,33624826,106413076,723597875,568390803,767898522,463225801,746125210,356916864,129027206,431180607,856201428,494571365,32448277,209801262,995270126,547088790,735468340,292283558,951245679,466890686,38621427,806829789,23553926,167184887,952205995,244540034,209676878,387593543,712498104,527829057,699704754,989753531,974580532,82183290,247545374,252829736,437026554,627114158,774052143,659822544,434636183,168001364,531437971,395768861,835929339,38221724,304044425,20540204,779025191,314325876,722713014,316642698,384499125,12483526,895510084,707518413,888696813,11830505,363351373,425188100,851808202,89601320,885487034,726376222,906302458,965493958,546829583,330100194,557193099,361833821,718373051,451591742,118319760,877983633,320518204,707099001,677148255,948600776,879178745,404503404,722596833,436181124,126047342,894932350,362865991,898084052,127951481,336572652,62489271,46019269,40456203,281339002,729022466,18785237,436645631,976150943,501413488,491253672,167772882,192750205,12226549,803488106,298085229,541458071,378385404,795889325,473569113,398560785,973969674,646735228,569819344,936667426,216052621,925377900,43579773,542899124,669675362,720695525,18539557,349596343,310763819,529874429,582502096,706571587,323324975,460739999,575854008,45384257,87334063,799359437,769791723,918316067,741297107,237392778,569062765,311493933,483945834,947026641,463533084,655770580,641585034,284004645,777290428,839393532,870032956,338468339,699543407,677619487,478881024,165178817,899729104,412318870,231911535,671835770,524758143,361419625,663272503,489056446,181597162,295713515,331326985,625967966,441547955,233786515,96227706,599463575,43152667,974525063,708305253,242838638,707919347,3235303,909349279,185495307,972050596,849260750,446345102,593013447,250619151,737215753,342401909,960042774,463596728,399747834,469772677,226199689,701354000,428519175,880232247,289493263,20954294,587061802,298086821,758122614,588404876,670373976,737966509,20341111,916471520,99974207,979592421,146120502,914046603,643266206,274425586,839933180,505835937,124490864,30211211,130190257,278754221,424709640,551512444,634844123,589314241,998955953,528226942,108348554,365479421,226826158,392446812,987288414,340285236,467657753,416978034,854195055,576382284,240854645,84636964,457035841,34726066,891232642,316120527,628576698,578704558,14298920,551755575,295165017,951748845,998351810,221598419,391233686,701411235,745675739,754006588,12265430,965341352,480497830,656430922,481912643,543741380,640521027,149924719,747634604,924829424,483725447,839999894,336906628,635317632,724720377,378564718,519709545,317904573,965356386,666034716,752849351,411710103,92259576,947442718,470607512,261006369,298458989,6469787,238125547,564988252,2523011,643188979,630627250,621775019,263668635,149052834,849641866,273913875,132663355,69782156,809718394,108140059,518177921,38591850,968025256,534294458,16277387,95151155,76762033,348029493,999560959,976299505,569496332,165739528,715062700,846351101,944487441,857174312,892228627,211324736,261773622,316276403,668106416,782723969,378363932,802755344,596671106,599098120,217243264,358547706,705726467,377776562,842866170,840174666,664604270,297270977,84990711,23273884,891380787,910407670,876702893,360157581,722002891,958048747,152876306,686693936,118551317,250865769,819359092,667068765,922195567,262600116,512553088,501860628,876638112,586590257,535633743,367981419,150990293,459082985,228019602,665572438,668355758,264555248,34773628,480000307,825965207,966820862,16459799,989631222,611164085,63094494,322201301,763293344,621240322,326086978,361397373,717879902,270425175,330956391,744721484,484387152,483746227,434449317,704284563,959201940,950265518,369225917,462194023,953249096,98751036,749084290,244627843,833584099,618833961,415831809,356838074,847164584,251658243,661926111,756401396,806028127,980090109,902254416,821424212,439210961,452180779,5159650,455453116,306485954,605130611,200204968,591475241,16097967,246333302,100857235,539450415,305808875,559703774,122132641,638243008,838147256,881363752,853704976,755799977,314341778,885063647,472357044,467757130,591382928,199625776,997504418,803058030,320516632,952629181,971766012,291926059,704183384,210373257,901869250,643358972,319713083,364342249,534165122,567245161,314730983,789098781,842095502,160664110,603460711,521461111,955019743,623952629,227469751,710797930,652759591,463299634,511192896,627061466,551514679,283810340,114924820,555343468,922664314,805852530,723192577,31448910,782621329,713823611,376752294,699934416,479318968,185031948,8981405,9373512,1414234,83244066,62148199,943705406,416108941,902544716,462525942,152570056,44371808,832595433,393283013,991250316,544082214,910272376,832121994,375576263,557767449,43756010,316226133,293325443,870696500,188311948,627399959,117656756,932150157,695792817,220167727,123913334,153425718,618578132,708240910,375980138,935179231,374775389,923545462,494892573,867276506,852769416,167527253,552434261,338896182,893489766,553213328,585252966,58140097,314396910,610641054,159967095,641564962,956714904,513317653,373736370,199688965,59435422,692707157,73749813,79713702,716211522,645057579,659805218,981110529,162997651,502574716,853546708,620053060,911077100,46931605,35453350,996204626,638595712,797729550,182999638,45840594,181999310,259505818,802444863,643484225,167018728,381871703,914427236,145449358,561676805,910067883,279476893,158173852,815949748,548586129,907157785,155379813,474575493,138650677,703079120,776056333,707618066,858349206,539230387,308289037,727946808,589066479,634760683,199517739,364064761,69207917,594972445,960588962,131174043,729443479,61531003,315916117,69677292,710076089,231783376,768705830,736552580,507182239,713462557,990407548,981805385,633606754,273883627,754406681,491702663,847674015,101638495,582441282,522811741,397778892,664385130,949424377,843049294,918206219,96875735,7815254,257715981,130287719,150164254,8027075,76465667,377363826,228567174,874944977,601687500,168361425,243387115,263389072,251887244,504762719,621113175,79965992,384842145,642337667,249596238,778186128,24238701,4115081,178151148,727317615,290721993,18944614,619869320,497829681,363457335,520652040,127069134,770641964,18238133,629311218,59023585,529237350,983872218,892407351,197852927,383162046,560688516,513550383,764463052,294338418,446452558,888547576,808535602,160849514,738517430,772587823,147472515,942939460,194008136,295880333,234847957,468767255,385146882,437278817,174400444,442374625,501062874,77850864,597168396,764154222,297317251,472222677,584975800,97056843,168942833,275887045,805071495,839261257,232366934,180445012,802373011,139510407,595786273,910943303,710190130,425043146,637354213,679308030,676961234,338282355,363235502,675625286,10999636,340802420,288695550,914092924,758354234,746828808,426479912,82021993,748325911,678302752,880307125,130726074,781485730,206093505,277619630,191309741,986095630,312129924,677192706,951878906,99517618,962043258,904755058,782834083,691918664,233404190,914327803,679886900,983510837,206776607,36478131,383021449,215812738,483581414,99578378,174712650,857541839,567095410,566314942,822677721,454360619,665715901,838492538,857141950,345915881,357424519,351700942,184658504,491708742,513431429,185644913,292291362,640270188,696470613,218493127,559806800,586964553,118836291,13874008,589715248,908120725,630332750,449656129,4422894,70984821,198114748,48809044,759278881,951599758,992765373,453659201,467223339,652018885,173738307,420019484,859476650,310827125,711940311,55090610,17758216,299340186,511684217,641568555,611730827,636364659,920565815,161619759,283166163,454047047,97313874,343823890,477208535,597381825,159270691,441267825,273283610,26737856,764071257,196224203,626462468,207931677,707318925,830520751,66743150,878891281,287632892,876709697,675258344,316314924,87044257,278713848,349722295,904155444,398544295,974317109,643846026,720585255,83097540,350737871,78253415,966084035,731450920,24351568,133671140,847849339,346393398,161551828,381906350,435623075,380575560,368544910,316057344,359153978,686122041,50530510,135969528,434384289,858590773,60151478,690178473,359377357,609486226,863111210,414783633,858429194,838119257,869398265,86112824,18149579,30074477,949872144,938389439,972116639,279491312,869822102,101487962,223732685,515986270,514109522,475055589,900157956,981472676,357397639,386495558,291211203,705758873,923459972,742047129,197125818,457475704,163416097,248598942,860755727,362903656,390473442,390970174,582780673,122795019,585325494,460153830,860846881,619327425,568571420,368954649,545411741,707930912,6348580,780709495,990904465,27247421,208295789,126799745,483057326,544006877,643600769,229221268,541451321,975532014,20979997,747504635,392077004,39420474,447579086,274157263,663539113,258477075,740294452,196696144,330886050,237723569,437762155,218453195,464547376,636522902,159628669,273339480,527637812,569833295,481310890,41861223,747410379,197520143,255130155,76093065,253443814,84191825,985677156,33020574,50969248,7241188,856164973,832600801,597067815,82118410,613973716,931090123,144438441,848189497,572675759,538936122,517884038,276663274,841803821,470374844,971856681,506342402,509924003,614376917,327076435,111847683,148323013,816227982,148331512,984428279,119315209,939882083,936523043,395904424,82173874,442532731,929500231,442583517,307873422,865687780,431022266,431801422,693703719,825896991,340339072,54705917,972701004,461474804,401403322,534493593,229763898,760097322,957909751,35755501,509539570,79457293,683376436,914423474,565350491,66175657,133727708,62689744,222220227,373164261,888202266,1051213,425986996,979586130,359010094,182057251,881634212,410320055,119969791,60808738,996431102,903957070,619045274,106103593,11613079,318552950,899505506,932554475,226221979,26325195,537811357,77872139,255179590,657927593,817595067,967542905,685702890,507433095,983971581,479920725,796217273,961718982,368484752,257392959,614980906,944206604,579823777,973200830,783863031,309202635,62595655,133275890,149413508,128050203,638331018,63245114,443135528,540019529,936484434,899148337,343918579,71708015,845820831,992893194,839743567,820102613,502058908,565415857,455745667,992857059,671406811,821531329,583859063,931520982,620830668,614162833,342349597,753965611,241739476,490322213,380890385,750760032,800604769,760196079,202770021,711315234,533064923,897881470,537330785,984697092,619887081,88289913,981961757,796953633,230316803,518596850,534527988,298757645,677260238,24721722,471922012,397472849,198668166,590196958,412197547,68911718,495491730,393789439,987100746,903035622,851205363,236299337,881795158,60640509,36301313,297465963,282817675,123653927,283406707,777729104,938082533,742271653,918931265,281629392,633104165,877762369,546900393,440330680,756095595,589986520,515857369,799860868,290230825,599010414,80843200,624367974,984234690,571403730,399758153,868126762,789161114,464005677,186669388,344487940,290168668,323835747,691430734,330749297,408821196,269798863,63436970,945010981,328962048,403941919,54857596,732577822,204814516,611794010,368252266,847756466,89283039,358407383,213182505,965931601,949377153,179908735,683879694,985960549,351928006,227004879,112841528,211816938,51837197,467675100,473810303,895966964,785491961,816172054,623924644,206020707,812073679,16709848,959561506,401857675,965174098,708686187,3930894,884410079,731739606,518441149,515966553,391572471,366723312,818222919,989733718,175384593,416544572,256466198,134151653,286957068,769431513,220928812,208497058,892673176,61996272,869271799,84520592,741095496,382199630,4100106,886151522,163941668,149606543,575546992,856839697,908045521,159765599,470372413,709837558,331783968,544730186,20696015,8940592,694160907,602590697,255394694,369963580,326466184,573121035,211939569,493371221,544387259,649165836,73196385,507956912,564241224,283520300,429246733,290016939,709666971,822686326,84203565,142521627,387893874,998894737,973888175,784033785,669079359,316632369,54130569,423442459,232478989,797603103,420154882,763166557,694123396,628572734,841791166,601907708,678729203,953358798,681751135,133705675,632708233,979690727,266299843,13830067,78186795,277964354,184599934,496845444,227571915,388656266,674588058,999576750,956583878,643680599,164103620,477173311,55313819,216997002,186540574,363224659,444655711,92936554,772049043,728625292,937154653,447200445,181888315,929802379,528086325,453855994,467431417,535721529,582886297,607372787,312507400,42182858,645809662,812277143,974204688,571024335,300958194,155187778,158210636,155866129,858149070,441854648,528721065,623316839,242683884,61638142,450134180,184012595,620113219,117726046,113429186,247496887,133168111,183342503,544738408,872049647,249912855,220932676,477782952,50438639,678203175,644761301,123159799,231508269,271977342,764571839,482849505,9057829,884852003,984870274,945390008,839616040,270185089,305044493,968394302,259217522,414301282,481844922,267554223,373628205,77181749,277005716,210621025,491799389,22029946,26190935,390187992,138737375,82282961,465751412,140694559,321907029,717746459,49403952,460107644,414018159,245183373,288145068,927766687,940277180,533194201,309348284,981350580,332859686,941002563,560757336,470836628,945786235,248656466,111785398,602518399,74156267,165701686,776278169,8183070,871641387,419325144,312656142,287538711,115030853,333260323,749519820,56802435,383841422,251000795,404301840,195247284,765388155,67840467,873869226,502974780,284465965,995915565,845710034,277766843,533876074,269106794,650204466,261490043,747523379,156723035,451869794,897949966,899764724,640077555,650958302,808271471,998105634,824085959,313676337,603486393,516612148,599543491,532744112,904368090,872327159,363939872,123297688,462835754,274011820,664864655,527696611,798390721,640952870,95784642,543620555,458758792,681527336,520504592,754242125,477758971,474299117,552300467,489987099,704186484,578203597,387342088,59507947,264287376,118843016,261845019,653833435,662231969,758667942,680994882,120684470,410594714,924553895,976614721,557026657,706058715,899388115,327959590,908566789,241292267,718538324,30927687,399804199,672908001,643847161,382690814,683673466,407248448,821440935,221327338,136640867,436557318,748314536,385286835,368054838,272767336,689115743,133219921,277976368,525522204,831904348,827711459,939999462,2501473,893546513,965480679,180448311,754778365,456004412,945647692,656557069,659960137,551716015,350212353,294420251,906232520,785181365,849768699,355737804,934909052,27396238,813124337,257829903,380020036,419355469,91416030,168931670,700307516,137250607,705524004,777144306,250109181,657013035,366002400,282828430,584737672,907432435,693180818,10225571,316656454,313837699,891741269,204563704,226641428,717240448,798665715,418688203,119080018,253561098,95754700,828005398,340319252,453958998,599025378,639800591,223182108,289239703,18169412,534974541,101991095,136528016,962659549,47153183,956902683,53414795,551031002,751680917,914586402,85188419,608269345,984713256,26652060,80559280,644799389,367093617,313626641,998674493,481755593,894741201,391876661,568856045,618033105,11721682,271722934,531190420,836538222,899487855,260252284,242329575,286665502,609901663,304219372,917864160,253982470,1183957,904662140,142179760,451529170,373180156,97209741,174549992,686274924,541878975,684392912,488343215,364439079,987479328,56216407,141360286,359042664,97207342,768838401,651446925,722836541,493971159,209096744,140105212,319106712,244989772,345207616,283528260,140738341,563438432,31648047,315985311,957821156,959325315,443546690,920966131,168129448,781660720,541009484,469961147,508471238,306508760,142438919,577255296,385027005,154575803,546189074,459280227,212506007,869464185,706028267,254659079,78593223,723291751,172741059,542828214,384512968,780624788,423047235,435369929,5640229,666120164,362854754,493898413,608899295,605236642,720284014,930210810,950072941,447076198,648114793,181990053,916156249,703335259,491932147,880614514,76633991,660730244,642159655,403346771,327087477,570047583,764038403,751167397,883329704,271867938,552764284,328655031,648394949,86158650,258723605,121586115,301799777,84813650,897642597,266902069,136317202,591923308,711757955,868869439,923382577,935351819,459569228,789361447,446372096,690466818,770566070,428584054,274168806,996442229,774889540,451835136,430614096,354657467,500844027,928574556,49692978,331759286,556009728,412123697,633229055,162592082,605919692,636663443,443248218,587736612,633295679,936747618,800403340,965585655,863231024,39553919,84884680,57220947,511627320,745252525,121933412,929737702,161726909,180996707,643978557,88639236,495952345,245184353,386742067,95971547,251335956,162172129,627426138,494621956,335051510,501856998,81951523,952678246,961367679,880195150,561763223,241247737,829273153,678393791,390390354,818542992,106826981,919471987,599824184,217461218,199786057,114575341,609337777,331208229,527057274,353638773,559395147,37520099,699557329,93189214,128288650,787812901,59236764,705283467,27794407,74388516,751138671,426976256,824815132,118801647,475858360,504895288,599533010,680580463,110686628,238149439,727443746,819962421,212103470,841792157,703918359,998122576,663691645,726196983,723885145,267179129,341410856,173400496,799531057,162609503,253260127,91622819,37911540,240096675,690023530,485416730,195586101,208108629,872103995,97843085,170274397,450662533,479552819,850661260,642773647,731711620,356825794,369963078,715115201,876717767,999951398,610854516,331750631,572691621,356190514,769573647,591524558,529882029,93058158,938081118,426978770,695827410,188291088,667885282,550792811,775238263,895661969,93363187,955106191,633185272,160395320,281313612,538872726,726613369,320460114,630462996,363103286,252994367,446847885,760071435,895682816,760968975,104707317,591851119,158665387,963465590,236827292,678998504,741937791,118320162,265348529,228026006,287008192,351675373,759463146,7908266,749042273,251515788,57713488,146152631,819853283,229940049,153880490,700088325,531552087,7364381,312403928,230871612,25718814,919863429,667823052,523993644,690276041,287176131,588197490,679501354,200177284,652957515,669987281,854303264,319640821,389313172,755282652,461630938,16267588,567041560,258543763,406597288,187434206,711916448,600882034,189630494,639930457,856289886,777793586,388050698,653527540,168523362,678029520,760549554,441528586,1064375,688551739,912413534,270751594,648370141,186999173,724790610,216627213,779359827,539953579,942333522,429203362,734564720,247520296,798548018,215884579,586065171,115255730,616941161,457516043,108334682,421570785,121564050,773560382,759028213,338465290,832166438,853277282,757387166,413202512,622924211,927701785,73057741,782738595,40756889,889658101,29328382,690052272,178355402,503106973,38357982,512202003,820022880,972290908,371837758,243461326,677709242,879873029,554285375,704026821,884346452,619409214,156636557,838655627,52791752,949614885,299667024,206503739,592434097,622604173,327838258,706202986,573547336,983185083,213933883,110366309,668277882,863182903,872598733,601106927,319201926,572884594,673993685,612484158,748950260,183281369,793393753,212026510,720998441,12756000,469898379,333117674,204133421,941971281,619883654,680546014,723319183,432032732,678569648,152504246,565474595,787481527,317659126,922141203,138941785,502331451,472257549,493204353,315052293,59527662,943693688,340393623,354600193,349595634,83409022,611731776,179068243,428392472,498103265,650844073,729096543,73803467,571870688,194202807,452252386,517494000,310768015,184290907,784958455,246712301,721092888,629454419,461820538,80346613,506424836,273249589,816414036,175501458,500381364,926442608,569748359,853301373,766280802,678521113,224616112,739069473,960015203,520677030,343751636,464565000,362744163,168103182,528749598,385551436,129674186,453878063,789238920,215432965,784395849,744970594,491712498,547540851,51887966,32510078,688675335,326565834,426520103,853213574,129750077,982548776,765740120,177768542,76744681,958163889,357517889,979841813,602901708,478499140,940139722,347222504,133449552,65372060,931116334,688972949,242574957,955382673,942093920,372836814,920252730,767794974,440697200,481334703,788876439,950842976,651547207,171007635,344297347,766119709,394957270,739089556,639824618,574583760,32931080,363840519,800449757,228628717,495177231,406464335,36397015,796175072,184836867,683863653,181010784,975613379,453627558,718902218,680505673,484844044,827124306,769340265,403174413,356721788,594623277,41380296,345650667,579938025,498327752,637495625,694569684,734088875,196587812,896492161,509040375,396134113,771450959,644888700,154368661,331085266,785831876,144065376,285480468,930723507,337336657,452577178,374550647,599093383,206816107,588404517,738833453,591505943,659791195,946297319,205488881,47185344,431745594,822975971,457508930,388703893,923079372,813318949,605019455,185830216,973541510,716467564,484395564,219829785,317537838,144787633,710152753,380487533,713692172,214116655,381935269,795230008,226515170,283555227,599414598,35674687,589918426,303696443,48005653,200852635,977322973,155533024,414856057,198643269,629903840,702712690,806634093,880430416,136234817,759038882,629377184,781320400,159207275,120511513,524959580,424690535,395614570,597433120,501230173,687238667,559903396,260476178,426256707,600779104,263941340,964268264,983753738,539400359,942209899,39087140,807160160,314461985,534465529,506764415,65960642,10577518,216163814,901848724,823979427,60534189,923183291,768126520,435291360,714562912,331802895,240895494,484825131,748393111,468362372,861316731,738858794,229582475,786722631,379669915,474122025,497558246,820204481,357181301,180605225,854780149,136733139,995106160,300154704,676963299,491753328,194198246,321604277,537662550,817999852,368677048,662067417,638934323,284904995,595243012,695098672,522614400,918053055,291050029,151600020,117807588,540170228,909826277,789958449,383729048,686806185,903198867,303106481,970352366,392048737,989883079,556315058,40289267,878889597,497825697,349971995,110983627,344372553,558463071,782370104,110454412,725583539,296657455,513523899,141349702,86786762,554134571,647070262,970558191,736442203,35207289,595274674,554331915,812992943,890633934,370279925,362077026,343650229,610275927,623249236,366306654,707211425,703807090,904152302,676101130,564443457,917805822,793212546,632362336,827554946,345181351,538955736,697759120,791170678,162392126,132209733,663561197,99187667,165787309,857103449,748551894,366413248,748314298,423704398,225919602,171327155,604062822,995580212,928290222,18434645,178118406,698497486,962776214,388942504,926885527,128799553,775824265,706226970,304779024,914519823,38433922,206222056,168068419,380446767,565060758,94447527,895866750,85598918,714537649,759892465,805196113,152247588,264647813,4442334,170952899,632981239,233075704,206486174,357791912,316267198,683322875,410674384,706414150,900211375,900450015,789321679,969600220,85280080,613623414,734278125,413529006,235785462,257978535,537481615,847147146,613823686,102138308,888326016,994044286,385864332,773993609,314410275,950463055,233392981,204415999,804217032,432281406,946004306,544829314,794451144,986079759,630585284,851364862,525702334,550797047,224069322,622602406,638463310,414150857,919421313,715876477,972786725,694955035,595751840,390124342,431959926,983282414,812138162,879948698,239636120,569386003,96114477,599152694,183302737,732976033,646920835,152948575,793612271,244957365,453479116,568939565,616059812,849509373,925132802,773731126,741412655,788346252,113183085,521251473,69394929,101451354,35606913,6982440,903852655,383854839,787168480,231785042,772737463,239852991,913228423,998673353,146615509,231314524,341777964,343524727,551507535,74631090,666809257,165783262,892216070,291454382,18866970,908132239,725030177,783237076,102954166,327641150,349798699,288586513,131963459,790400271,571489035,146896574,713577162,366127198,107750289,304229378,384874540,272643492,524358864,181106543,451332562,520993171,36665219,684310725,125491713,667108437,75381207,441758230,149455876,658778280,55252907,793347739,149088029,586750715,454559585,259278490,293329694,5285524,37126656,602099094,640553440,66351579,208585717,820307075,826589893,707966432,138182823,760374128,310310446,676269389,995295332,781630206,781648895,649669266,852904998,666267867,909986705,636174769,91197745,623168566,330185702,860191847,36570918,100613750,247453846,497236615,320724439,778829363,433917188,214725100,743931254,415490829,643465744,859130170,994592345,494983240,638311067,859021674,377319534,571731665,289243640,511565940,671572297,998291197,507520101,528542127,836203783,293476269,393905830,173547455,486692044,627089413,241303952,419846294,235397814,712658601,845025758,472726294,655507524,401044522,548969927,527868229,667301639,837001593,866378094,252213777,557600117,24783534,427778554,931732224,490146677,626351265,398664479,349435581,623679381,474973453,921094698,954288577,48226213,439355045,886736841,56835777,973647431,580184468,902786221,608843553,387857580,50063259,354259334,671831724,306092282,617221295,612465533,37469721,284568795,686198548,287104603,35214269,187559160,89765465,321387295,880377396,323499728,916540162,43645079,122261087,199445779,114314961,791305015,43868775,170816228,488841167,772387093,898409995,169852706,780066489,695690242,514082527,25423193,828583486,233111400,928011038,717197505,510545175,39117479,831814380,524462887,932721037,406216103,263190773,868155238,378503957,487974460,273238568,971606383,697732922,853910006,721441499,90138425,885661504,769909051,470287596,134495987,342169016,572898921,218296112,170703065,940728006,451757740,909006937,564562118,927132254,811339599,569800965,769377384,296277540,597939004,989545126,125834931,114618817,274111817,747327638,778693282,240825461,322604123,906599726,264309666,351896762,818131208,671234797,680681716,761013892,430602836,597186741,290336140,262351744,967009935,642021912,585151994,957354150,82520711,814382619,958104487,861252099,790697627,91090058,231067660,538710922,737867926,620411394,858813938,705416477,22468435,182713789,775673374,590289166,321791537,152605751,452938938,660799714,818736518,370929374,537087188,78663871,34868507,479099536,80533064,525920933,990481641,105954981,902591852,426904546,927320126,927392967,362669607,913652009,676194111,845214759,699800107,21333253,401732222,239725440,112844911,949286862,482752088,682018148,733222727,822112068,661228823,620335151,699299297,97639577,77534328,168090275,514168826,45250159,179868598,502938062,443695928,803527034,468022051,738001914,63924427,78451860,315652468,788438806,779312981,655179131,945303594,549260552,272861568,154150588,932666926,512692920,58075715,477494444,506830784,311569164,256160380,701850817,614507773,22331312,983492781,727825428,595212534,436529569,486624829,397971515,818208758,217706598,901731180,755963618,572749501,225301842,165795130,910657082,810702727,763020777,267138378,884455296,238237463,854486990,452767706,172959369,854164113,688891758,984804146,973469630,196257666,905634643,924622361,102721469,465334540,656783329,58058213,588604595,896144059,825915360,232903989,785319349,855156288,80633342,137138627,820551785,873350021,310282230,607479072,806554815,621591450,8639253,964903573,551897132,53464716,929876435,408267902,715191055,393471257,765482080,119989603,945734926,515415450,277616290,324014620,732448013,3703339,257702071,482592178,577669255,257753697,715822280,842226349,974614681,655389557,797194930,332444046,442212673,158467505,277429837,191973265,519729453,406273587,821151381,197555294,327018466,5767610,589849673,975735440,443643366,510878433,672714102,871050050,481518838,806358974,133712387,596869233,279515182,352753780,712949858,447135104,53136863,527350346,362876493,576958868,801017292,498175737,478163226,262929304,168249387,742435630,355830325,20007196,709904573,160422410,585357102,926071893,496923322,69283096,828400123,891532575,461595808,195146384,383153833,387268046,654148497,996655653,448659729,562698123,286716745,751671118,132030377,613988190,858266742,678131538,904897605,267985829,769877354,320594348,62388143,853024190,303110420,606890652,554428393,191285051,909562281,775300532,541705403,276095774,148486856,919440572,648113008,381067382,807303662,504779652,441520257,594955518,307187468,487441360,915432555,149192727,566204771,932045651,311826957,683162646,932960450,263118774,985101961,159495831,962696559,561783709,620488574,791408245,407229117,847880914,193410940,589175788,777687954,503724650,585411169,825872709,10174861,730761405,568018632,626380827,405833731,351178877,570995360,914819148,731850715,318720178,477763207,615949658,578263766,620318565,244056976,818486300,275407534,388343832,724362623,409158687,829726204,592037378,878961313,708471944,317602600,626823267,529903541,152336654,469555479,340318550,546645384,338308073,349360069,230460746,210878037,166497983,783092823,664027806,734055697,297760351,809688181,123849657,486280216,231301674,75384257,675836985,722287645,130850162,560583179,214891552,676569639,281572457,826251340,960119231,642481391,121120648,573336586,281713631,57175381,89654384,657876593,373069560,937196598,219041832,262768672,90156906,852891302,200271308,176265917,898072451,753737769,571846745,639816106,252301931,801201625,666075521,447865236,332170850,147021566,564593578,431765846,92191755,274581773,664191467,738447911,254071712,288544534,40642391,604323000,847147020,105770126,436748173,267566102,94994648,395671143,860069685,777680967,461142840,727558385,240139205,189361655,811396658,243058042,676941941,807224888,908397559,29244494,796774925,61490884,37928771,202950947,887325333,896012096,799975611,467677951,68010139,451786560,115052384,307026582,768848590,811822988,812676924,268371386,409388147,184393382,427705571,655215117,126222325,236540401,95567182,112421037,791428263,363153894,173568776,15729312,924165731,636333911,658655221,717344030,551775773,72288017,13694772,746093099,189681099,977194888,79967741,133827762,826253282,736704075,525875874,709859638,700592604,132549228,605613437,45799734,861072716,313722311,312737967,66316053,864757163,258066879,417597110,694069177,181872218,263419118,201530749,871727940,349774995,772212359,679532739,685432863,590851098,835489446,926250870,590993960,647718380,271359911,942116257,494433150,141322024,515147038,450820434,41662419,387611690,490160556,398589966,759708148,244121965,15842843,667950508,746490973,351399440,723170654,20251181,270760679,685808853,378385358,49914903,444341160,212940119,823914092,284670187,871631601,801471821,867394728,392590682,20359822,322705731,495344602,194237166,933754178,582698273,600482211,361745308,621274688,578813896,100157360,960966588,513066885,805053952,384778809,150505400,946791300,902711564,493882509,702093589,258771373,237224951,413511778,246829839,251370992,942413900,372060772,251724903,502249949,499569907,381452750,877170925,534048716,789283110,432353740,869374007,71730275,320226800,918944252,943824917,409227146,534154461,975577493,337634402,687248864,582051582,380915151,739400491,62378683,710416673,492118793,274615801,504694144,879980925,549029143,159008158,871425836,291631610,893381863,872740745,897431583,648198770,114375504,939647458,838181978,61940774,128268035,404929068,16444449,596300217,3660173,79677142,940009336,420954829,477012894,219920187,316928842,413393420,258372625,13761433,714722596,193087091,526169797,750388610,632585924,772583136,123545609,516650253,732645306,670594425,510422500,995944621,611436674,378419604,360682139,729749753,736975625,443466512,844333916,118800178,15122610,15612394,577570635,935020249,189767730,325384730,101642113,507842258,523303239,364314591,37317725,953354006,987088323,605318856,700398894,891588022,271894832,317482439,998419234,828367785,455829872,506606882,419210975,115238363,888370518,444985134,221485890,149439301,713027331,395877620,985624767,443764328,869105625,67033478,607662297,152577635,718540328,301199095,393575491,922878806,75122760,259181700,680523990,111130121,669656816,748798368,792922615,960128661,640673492,933607107,891094884,686131481,371493272,863088412,253142063,133585759,875652791,29777491,227333983,638752359,932990723,373892892,363533543,19755480,716138442,282763051,123450657,897467901,250583512,396865914,571678992,298605060,620218400,787571838,730515296,492271998,761755662,899943784,945389759,375806455,240294146,772294281,314761764,339709350,56293925,669837459,164968053,520971482,851917115,437968016,859106402,148850331,229489406,615408679,137068414,798306110,989671565,673460381,502825468,955057943,358286428,244656794,364986875,889800886,285958738,484715557,214285173,282943840,681802864,907139203,510903893,999247245,978013723,781357369,27713862,533726279,242298435,163137867,14197256,503856768,867531205,612640535,49416988,672060509,442831167,66453477,194211827,573129704,223348143,115671549,960079132,467614529,867147752,639987152,387340173,536346429,98921047,753537278,452678683,873088457,197619591,3309875,69425692,6249446,152022001,434948568,398895297,473136677,396949639,430469978,436303698,759807288,19380055,29062723,948110878,175473491,467071903,454412100,192683752,761925727,943409908,942979584,950174155,713959721,141604395,550402007,449806474,220676138,1418381,69337947,950570154,424657333,708704420,366974469,678092736,257481726,264672321,482248273,320375322,308717664,75968785,35879688,491591754,576197685,153155089,243663886,955819288,760090539,784514729,343021290,787067956,214511408,339245402,693508127,947085981,551870682,953919513,924386328,469985004,664330347,287612945,60621815,691690952,120961888,368392781,289905026,596472679,502022700,875619595,654000679,738767453,211234974,17818079,51513813,726625711,596352431,180064735,461980598,426775007,802901122,492320588,761308099,252074806,920429123,151751403,808433121,350709759,804452590,880196041,881389919,206718316,858274205,467830587,580369332,317106036,798707141,613565420,245138571,102995211,413477021,535587675,183078248,44695166,76302844,760425415,378674850,827617536,134104540,510641576,372687536,6856622,444421012,904577998,272422937,706091027,427170688,737260246,81028465,908563874,977229660,47855343,782647574,745355307,587971517,628154043,548178181,214802254,158680609,937756592,442588007,642531929,961916839,742135472,695012634,152970055,626119397,148355506,589831628,532418500,26412834,597718844,547078319,395968893,800163935,727050782,182167362,173945220,898788851,996775585,856712001,803113100,523461810,197630362,651119001,960447096,921390412,999887506,479244262,890619989,483904344,655230204,690137085,703862072,218753066,889966600,991815055,698569519,313441520,214315060,811283716,16083205,886785834,390271010,110755550,705859163,985302333,161818783,340248067,995444826,48270443,381096998,563120027,918299830,770556182,38492561,358238034,963788585,862323302,161373080,213163295,716856204,712167728,163503569,699501483,234289960,847545800,287689948,344971632,317775204,166111381,321029437,820201723,353464714,638658266,269280035,534350347,410342083,100957254,503089994,927834477,537090301,550217505,490848491,549004401,295279532,954191853,17618497,642240305,566704105,913118057,592453083,892785515,335948157,523687456,587315054,281568435,304569329,322506479,51985192,412504633,840975991,210706042,431151858,916724724,282515429,302957698,680551393,497202210,828357603,900882521,296310306,992333029,120168858,880632818,603878719,76787301,155107544,609268063,143636259,440980842,404510534,489182467,739682630,562186681,773598190,770589084,498449948,463915706,768765680,882866234,15015187,515001111,986112053,839586851,288984775,430560696,729684645,546022839,219712746,286535653,340826320,547639849,627720432,265410679,324755996,531158408,150990551,641052685,800753176,156655897,836890225,908792544,827870490,969392882,402209041,399654896,393154563,623455708,110332834,317457194,527033557,987075755,414899881,183133774,419897412,912530334,438116451,232842350,821173488,581099101,557751500,697311379,312365785,583810223,756281825,886916662,818633015,355145410,237231409,97107011,61455942,760993544,281312036,132467293,86846937,462124471,417295715,664540466,840013583,769988217,944022286,982073072,151996741,438381654,306257405,550402952,386830975,530271227,957024195,772727412,699854349,189597120,741355084,398338911,974188775,557310233,764140695,786385196,387563808,886835080,923720703,828188322,489444589,731428176,430666241,79618495,700417443,434003470,257880394,644317038,140428487,123398208,57809832,809800943,723664912,720017253,883063065,171446683,899327354,427070077,984405242,19512320,175461078,330988912,785541851,438438054,548995252,842812530,272849321,602843618,489535196,252712520,757433635,782095433,610062449,976381863,2915630,753101791,258880583,896931200,224424344,491750244,832093128,778063471,279589745,365972562,599951051,324221979,389679872,23867820,9128311,793203562,328418498,196105791,498371554,54283713,736630348,357894394,954427169,705957069,212676557,655344543,452983205,449464016,431118217,435283354,997715919,630456706,615252453,379586544,64156981,401930516,42233362,855238719,181469802,941701600,989355463,704437879,664116903,246852477,724282760,389156,762690629,80605319,130371894,221601767,382664272,623774213,580428131,125905343,201247536,910082018,724922840,591377610,319905706,500720293,530026307,527895230,880256563,309594676,938237500,351677182,522095976,350107962,187945018,839320758,559027671,589917916,278906143,538091109,945556377,691260918,847060623,527973683,804009679,508945506,586367652,907281172,96537011,117095384,737093905,333690847,672488611,812985038,273935461,147061948,570400050,918090877,775665781,690734483,796524012,328965827,761531375,803402194,972235745,173259931,743406362,521104453,478560586,864826762,286896469,683053262,523570044,278930003,304453912,91855887,474262166,342367939,566826501,46371256,1647762,71784693,723941687,109097224,344105324,541652769,588594208,761699956,562025590,236046133,482075112,215601000,136653480,486851344,463693398,140935419,237661062,81551250,493979801,612045708,492446692,670741457,126393061,452090817,343953892,881855220,124824950,180426939,188912908,378412383,541133191,205001306,442760621,961556537,843289565,434348825,413060174,750223508,316300245,885294838,836433128,499508770,181341681,379972996,737570941,116690974,75421687,13819599,632401199,998867971,752175039,590943983,406086806,122282583,563687483,579750193,720874837,706963116,573603133,207608152,550074638,218851092,735285307,590354984,71117157,651667032,925504789,989847440,227643203,835386652,410586513,572481691,515743780,792821301,151557455,772899790,503147989,454758429,997176490,808087015,203690708,261084398,369710866,802097609,473714748,961417266,529254249,542741450,389734578,412544071,177991255,254263635,620351936,700085831,980399622,492268873,701978949,477217664,689117428,328126331,342574496,862922123,841941933,382696489,165279484,657505270,528525024,554109088,223374805,387631085,930762936,870644330,680154695,639493712,373998901,103817152,127577647,834322827,902102853,886630330,395734934,784612424,483235786,830869191,576079042,957621632,817947619,767108391,54206688,584727646,950022628,239913271,492842618,399711097,66965028,120803849,89287726,802191446,1266057,223456985,319500825,32932393,536866843,334695048,831710354,399803923,982822516,880236828,348206275,510894627,872683148,417970910,111889499,342004575,728440615,238636492,677968815,191958540,358506604,491660445,621588579,620851321,236609757,599045843,621866428,126184777,367798013,607033345,591857655,268796409,66655233,682105889,758510452,279432085,703199962,329680064,802349583,258345839,323377841,968794643,530628478,851286092,144429516,489541646,147219781,955318417,736666000,449048491,660867865,563409841,348721900,317356961,44960565,598368416,739482362,45593351,7337903,522213826,362259523,330449804,731158687,852214121,7213584,414068553,542241097,419922657,145817067,16331444,683285709,703275650,515667327,479915889,553074841,745377032,742604256,893436193,496467122,274765443,43918024,991469419,152935307,244335175,607175505,101951104,216988482,169740410,331615360,132023189,629609250,256907285,403961258,232414156,58511225,172277873,897995887,810606958,984001578,612899026,844069711,690681454,680100348,325645958,49843945,190656122,210394108,712860453,897345545,613389661,651358634,445547032,685200355,234137380,908359012,290016654,321785203,470976376,612802364,940666222,921024606,389317479,865234722,80812146,215635793,722335962,376332517,831750473,94338902,268807006,257587936,28825567,937675814,866498072,564119922,668708404,893712186,854204111,363065553,638447017,943269967,317461577,806065067,51503985,102363479,482099409,252416337,997818974,744142366,306205440,833668956,140081755,658904751,940086272,430947744,114697049,600887528,519626498,63649584,414650972,246603316,721359516,464966182,906460148,349685238,515305930,168195460,699791668,315120576,973681294,232892317,104265556,697892687,172176529,412212756,590565827,19127653,416546247,860211736,875108073,353072705,173663487,287184558,525167419,629925664,214457962,781676598,951018114,573659231,106790800,928745611,193096084,16002267,917065388,302337576,817909794,989054034,391543690,559081138,297861222,57311126,197099723,259199766,486283517,745300845,856383954,121656058,952273336,481177097,577172463,934642158,373370482,416859827,830330490,230469421,77170728,720773306,859449442,285158078,238492920,975611575,841656219,587348778,413424413,592843978,932173376,951996331,995009069,37135301,844483011,469480990,917188765,223834077,66636264,379497578,684569335,915864774,406914849,384270592,582322422,115758917,92393530,419264160,547032961,807341397,819427929,4648339,61496714,557901237,4817045,191573779,467181191,977055608,704613049,170605143,513133594,771351817,207359200,550245367,575154964,54249335,229537695,857909162,763061431,232326096,230978437,425715811,404223934,314921124,165588168,381762290,670691825,342210525,291671475,304690930,717787729,772068450,77596211,571933641,266621115,146564291,201796261,937897462,643495168,726587071,949732657,884653764,312075106,904409158,731394781,456609826,637849605,542879371,28437797,384654835,139974926,112834862,104094612,876040042,204763029,742776657,38506745,867022705,269492541,287831507,642799288,960790771,435926623,217182892,62666850,847419918,975955022,715702165,295888402,815438121,499662919,623049992,553890797,699004941,512360254,233851754,448097241,519554086,857985397,724258384,928088009,635264016,497098238,431918040,175973957,591156438,650724135,780785244,271601931,415902738,91040710,469802771,95986161,970723840,71319557,771240052,655983130,724621410,898093790,944185838,88042966,389799622,738464111,194874444,536400354,776557127,846184098,36458536,451245140,15472076,304591227,254282830,96501374,998813936,46846867,21814963,1017544,464557254,152910409,87823457,648211465,848356731,377308032,749947622,39054745,850371166,552120518,725790376,164718125,147386567,196427073,148588627,562546463,649883405,704398864,827789257,372974975,734327649,627785840,111146668,59936824,148431142,96832176,228794121,927892735,314381047,15831899,273992406,873522470,322140930,592665691,713387686,184127230,104087063,125299257,126792841,799311061,111344033,660605019,407980502,740981119,153641988,135171516,580118982,647077806,912540903,348151264,994777916,589756738,905782651,231428001,881397002,411820014,450275651,809002260,583227626,878170924,845210862,309988452,754993715,125864639,377051247,699755913,187858973,880182134,812637187,120359033,137288993,662985143,968448768,456770856,476006857,906053602,391739823,477200656,580370762,233430525,127572185,955933811,459252903,563110585,408124002,812181382,760159426,6681681,642662455,144732317,216817949,573665280,542920157,387332858,329732736,329599620,445291545,998740883,406783672,334055655,683836800,559021387,464990791,121599923,227190311,209817712,293310617,223734025,276368010,791840610,955297101,52075345,186935329,532692848,400006520,105808547,189835680,843965918,950438925,671816051,927802294,483578981,402153205,863247537,152293348,801225904,729734702,496468580,513641594,927552560,881598798,428120137,461502707,289966289,356716623,111252394,936592001,307909530,464579920,280436895,346063826,664685000,233528863,544117076,371592008,855656780,3276119,558284775,905969199,496723912,393402333,29886261,224896295,37984670,801415517,18369583,793467968,643605758,388613291,573823284,748241312,546562586,636870875,363266841,328967048,950237425,899746130,332481702,310648286,5621722,423178142,511249125,323212181,551946239,90041027,151168004,936791715,226258475,971586175,11995384,229751875,994152216,554141717,851598303,725329320,658809537,684614081,775127591,589954912,510858530,521435217,32904484,932690180,120733359,884149519,732001180,901208132,441336532,898607334,406686143,172397052,548793768,777031646,85205000,998497839,187493705,653356337,638840114,452549748,81977896,294711673,453908239,241047106,85433365,278892288,506086996,753348358,854674080,601629757,105354348,699198338,92919941,109727060,331192963,866040223,708372678,250449451,944101897,268431593,362908312,564810736,850448312,610771442,96198098,783618449,473761309,67246658,266086958,956892335,834129143,351955525,845925874,196279588,282971460,764620475,137661499,393652380,768616368,459661320,722518824,554625712,122269118,437810420,332458317,847932677,426093663,978167067,867994157,96977460,335280017,64827567,266308839,513677164,530523358,448654187,130171505,7995304,666517002,479644328,793118515,492755974,299347536,856678680,958671516,88810224,504514701,472806545,292438083,531517916,776707140,191335592,690978577,408604347,545785953,153357654,200123234,333560293,390730867,706434597,275030205,454395397,768649312,168307808,888183404,763387180,229960442,197120362,697243350,156988339,409027276,727457626,60447221,518697231,430931956,536843870,899561233,159456934,694151697,343464380,560904685,674509661,381765817,64816160,141099910,300822082,356881723,837084843,977271582,792144410,252442304,338978321,392773929,753143661,865711307,171053087,617266776,256233078,518981247,970291393,147405986,807747495,509310039,73835720,290964013,952197223,237144476,951508307,243766488,304901532,578924008,881435719,789988807,74706497,513330096,204698617,658021807,604937085,810883307,55154316,364355778,85440677,441051310,983746751,488590663,926943105,883113834,978174156,726325350,403949287,468763726,873991478,241210605,824645376,391145258,119881563,629909334,585882194,562161312,783040661,881888080,959809044,155775113,725060891,730336667,29857273,655073156,71265384,154749007,881628996,516826675,259589653,438986745,208706251,269929551,812608084,744486489,482989438,818949617,702909565,40858886,633897120,142870522,565483658,446019268,698608972,978692100,181571802,724663356,375149948,956051217,493074752,29550710,581913341,452708486,20864278,293842049,65015267,910413848,966546183,730968026,691747260,680178070,184903892,334660871,192336560,375362598,106842702,795123627,227065105,164572483,568994748,272986185,493585206,975998344,883372548,101354959,564113507,149934327,853577520,582178240,537644438,698157015,919337247,535817527,778159562,782212619,949545469,625521511,849598315,34922575,973038158,205239840,966212659,10120355,348298357,94486045,521844665,99169129,890039222,148992117,981874166,216685301,53614804,358484110,670360761,448635326,4271745,508468815,633082748,978979521,900176605,399005593,144147991,466582640,14821542,308423550,686857103,213590789,123895809,107416186,720540547,570866192,209358815,920060648,609301701,133217566,208711308,87339561,518395742,435738574,319845163,314808646,132518963,468788414,463294710,404334908,284116197,711142983,630237830,214093191,328374236,382436830,750208595,410331038,131617244,742595584,801574196,38425635,651517090,258812321,926111416,562956272,409448477,875553312,524036582,66990498,233111328,110090759,119965726,358766837,318021932,177911283,903940706,831356125,41169109,987729186,127533382,503710417,871096177,265175937,719790869,896188204,18331180,479126418,815858925,621233814,876281210,881593264,769898906,330190229,210323219,989635713,308648808,916478829,374194492,249966620,61201137,910739806,950009594,209955193,699175048,837959897,54900542,910734727,981710461,650071753,901669403,713623116,265179690,71195984,840197613,780431588,853846435,205953732,932271308,259823054,737294527,240251106,437495095,88274041,523719443,814423935,922123984,982938088,702416704,402294754,293242605,552818664,507768008,940548328,387420825,500089691,702912696,708902430,852353707,512807420,376115184,107547103,589041100,740439839,863596244,45390985,314029050,106574115,383395094,19974980,797810347,971717881,914707025,773601330,605542472,359726742,862042579,859548371,296021914,853037575,592371282,381856624,835471335,444605942,573813305,825801641,427613375,1134284,511842464,678515557,647612989,871935832,94357485,465195263,434283148,38340796,479491681,142345301,416091594,682129807,444000292,866512223,420961399,579930602,472950849,868277959,753371739,531007652,752938988,35513067,671841841,740119529,842999717,900092691,842416469,718967884,661600881,743224101,263495758,600666095,601358736,249017207,48992736,368655165,375785941,433788778,899738072,207977221,679501533,103122548,942261585,343654116,165501775,805288742,293201348,419354720,178601472,983392935,193982009,355103677,815090874,199257349,417795954,603921962,498326294,822782593,783679032,388490221,15514499,615791956,309608762,206446120,705830682,698135627,504893879,826406813,865211625,141117478,353652393,165007490,557218541,935190154,190646157,592721416,106169415,459528681,571409156,509643174,714527660,537623797,506779391,41368419,8785064,663306613,713443517,644051899,537862764,147238144,97773791,764901205,941844042,692855535,493819875,676238261,797153065,271676800,758933683,30741092,548107880,7553180,93084230,724835288,9617880,87153125,231505376,515269146,318312525,66833636,957601244,926451357,591711765,783332499,653945092,824047156,527372239,342976551,135333364,337707097,883356379,742868479,637720217,724825938,107867768,31715465,421909725,460150556,441442228,272108440,496102222,236376381,705569981,69198728,217248639,610896291,681392857,159137355,712888063,61195802,167906458,753476145,664475789,219684045,494418661,901093552,258391463,304769034,971075701,397702364,904880661,658059978,739108268,591608963,830693063,438127390,175055181,567411660,853410686,347779101,719690141,260282005,63831426,154102324,143161264,243360214,228601765,479594335,981633499,626508376,188778358,673519886,966198613,308829412,435498703,102320381,901027992,141791096,344091241,818712598,86725279,751918660,79928464,563730884,669196700,27787076,275376522,929282058,381157458,272376624,203566329,888172747,733334776,426714673,785877281,215351530,413511143,464692229,882881539,831515910,239589704,688661873,835226293,681242208,26696640,618251372,996135137,538057063,152334566,157136588,209269032,837947912,136769347,756037447,919669336,311939492,745435337,483860463,614594446,255327059,957563056,201285035,516001374,667970119,192729239,545904361,140554127,755173203,125517204,631469600,278783097,484349336,53340070,585323589,893291005,433070171,416036198,892937404,596220955,31108688,165903679,161237895,560609342,993091894,577317717,352146554,950701901,691103561,326207267,743897118,139373342,771045120,440148924,186926142,326807255,89901368,988802572,918430295,482986235,54560939,722000516,772674073,113830623,241413501,289865853,528524755,624219191,648197543,870008504,860030251,454901118,286653229,841286605,221210423,37296521,49923526,200792859,517711652,770779307,697337185,564945845,232797953,418222034,435073937,914074115,488742380,257986238,333510280,602641212,512324745,862008381,91665534,595997351,541766337,400587264,580462425,531604719,137519885,839393815,455199018,636781739,468733180,551973657,639194490,376746397,444366179,244018033,989855813,350107055,482778600,921215043,485194841,58390480,248300229,448990063,192241193,270570405,103010250,240192199,7829874,478531036,899170108,722214378,936368711,327525158,487832130,252994908,649656241,764700609,299773305,330776023,409353287,334372009,651358359,132532716,246669399,152897272,23021,988387150,667212734,434984967,532581046,770825742,812047098,284592398,600536507,178257683,938384475,833631624,23055910,794074572,527007890,699422579,256851938,593545943,50321499,828507127,863322803,982992155,258078366,438886653,649720528,420969915,909912975,437948410,360995845,425464950,1068759,202166203,447802172,274228397,104665513,743275402,413188777,292284213,850334430,499585131,545621048,220387465,662082734,563606713,240212477,258787071,226502739,50021851,708077197,341589917,996011484,794473811,782473904,446465027,403305495,222909079,890990446,953322668,725216023,561137887,359303266,445626570,149752256,204275471,532910437,363218464,649616575,775340830,893439569,412657663,772505107,68309626,960083274,528360791,781631801,65117662,268787591,702805571,162423940,962606823,242477917,164479384,11972944,643737500,254389561,942818278,392311423,781371692,284558146,622807103,748159231,889557735,183452750,277856236,388850862,340615900,748360527,712732406,587231314,943942605,778459840,314920537,869519509,235127657,818989965,247765975,243299166,850568987,857764510,684920095,733285810,327321128,519850732,577363809,504028105,283265438,25147410,318629387,345329003,718913674,118768474,55038309,852894123,148965412,21384646,357288068,556723886,922085174,598213921,956456354,295533107,544285817,101989171,84759314,532537921,638455676,888623017,658879572,997540201,726327286,420987622,87166025,520314771,877873083,981661843,81434580,592730684,115982032,394227229,39270102,424182897,151548876,724390841,647737729,937964590,755290863,182788748,708232316,859481009,716293972,91569161,795257730,938465257,547558864,849926298,638208292,582985158,582798261,260690006,172582138,52428757,626434223,277562388,504992539,299893904,514080327,769381710,8293793,253203922,289796278,573313645,673076171,684115812,810013083,419510043,94517928,221962558,490838141,689740396,656653312,10796421,496256552,211866406,223739712,151074047,670275860,794729130,742646578,195041911,977349085,321895719,416497407,507092694,999581982,942858955,648632138,625140212,776912866,206903133,894920911,530184028,853593609,706637082,143537374,686195029,288830224,789893624,614314362,543911829,49510252,159684505,664508325,367037445,169032969,811511030,618964378,244869989,389608125,949730743,383474078,801223337,465887471,845932456,932781451,703793344,463346633,166966489,78441374,874746955,899377352,505887140,744006504,323276087,369882157,460496194,322814139,968417535,63177771,398354331,289127869,446734671,825385360,217375180,817904126,583519191,812743593,379283848,412995142,754322093,496390367,106541316,391766634,365258891,226566857,138895670,827522489,693431687,430833973,557783889,798029039,412821680,50201391,431867878,303200530,351163559,728944065,535817631,483799612,255778250,400209099,624759330,340892105,315015549,37314507,406422845,794105784,370736835,325028541,678958894,422084083,857768012,106753427,731446254,590876081,261862077,117633687,662893902,428372458,582090106,789408049,53929501,482684001,757689867,541467876,964504018,794310150,917408685,608694301,376723033,488631536,879006512,264376855,202600325,398305054,806912243,163805980,847069014,301298190,19979211,438762455,177009354,560811559,855446388,89330443,19116781,937620988,523762745,920733777,955182082,964561025,356026791,433501336,642335922,7532674,315795418,215738785,361991375,672222207,131046274,210948031,26703802,136317901,248951548,669663149,436537343,759979492,521767242,979222857,89543439,759718412,432656971,576393164,854269501,479059023,460716971,245557991,26360946,873326528,675758343,921469602,469617478,634938853,33867315,92007049,194234308,709479705,843907641,617375816,292595056,180368661,214718352,163540585,589932291,871999101,312488192,179841584,469454460,282622131,478035971,346244278,784573403,50130919,206861196,930800322,895148341,797432479,609092317,891849124,592000255,978460376,121658035,815062781,257187327,913328545,112328484,621688198,284577246,380895222,703100736,572494383,467208147,437190512,48359647,798475596,472936027,873588367,348186233,759705502,783504678,767305964,604328480,186663773,270379906,886198814,740217731,931712123,755821539,680185424,435518788,103172227,395647328,350863640,833890279,433275291,632304561,518602212,267869392,918263414,798845403,748426412,109846495,57607044,4063110,162426874,220886003,808010134,955765381,428491598,343492627,638890066,9071638,206543624,750479090,811815127,222764429,786386033,735152022,632726440,487729219,505161686,197852519,968216179,76907458,363193446,342441618,531164960,391028523,599286766,243397094,569759480,191929497,97047177,97069822,24383566,794140902,136083531,502349092,48749890,710100342,618044174,703990644,89429328,352390261,28721876,847689800,883555397,380891969,788917798,682362941,756633779,664358758,959297836,401256547,117141097,674984486,378847571,731077757,50286896,94982958,953690974,512677100,159443779,984267995,277855063,526879080,528929737,292837715,559242044,518520991,611872351,776668507,797995237,983564445,814027497,17712300,679695945,255069660,762625964,650522618,107174172,248349309,296101172,258537063,844390314,102332665,281118129,568283596,25806947,540911918,255212002,753835596,589823082,34758129,750851249,676378228,785414570,692276250,591393863,431086661,41314106,253944885,245926827,508117341,849614165,293411654,435927713,816314247,753654680,384225466,272545599,994733122,210450080,738655535,134565854,498013262,191211348,35987135,344620288,935051904,884243243,481017207,445878346,513768068,481238939,692070026,176254429,954902418,579374428,173329616,209985678,581250421,952418190,440939367,408433549,267201094,174546769,905916000,605451247,840785780,232955986,397167614,723449849,179496056,277596072,583923132,401866006,907829746,512137184,884496543,171796599,193885584,390389029,690163259,96163401,558043657,378287489,736648083,816314841,927082604,985114666,399217115,667352651,801980281,575902707,564230910,887297968,58041776,360193998,618625658,195271376,497153271,57800963,593936550,722407994,260672351,219742085,283021943,728161138,282419926,805653693,865948306,412271915,645767516,903053291,666559716,864134823,76201440,942983517,821791379,498897702,536126019,738586862,240097097,509862090,200609501,423646169,461793124,43574669,406461222,759226085,374516588,457061185,217397280,594626388,469732011,429589596,382465622,102448481,964500620,672456822,56304524,315950873,597853010,100330824,85625451,919690752,350491660,139581788,325589946,649983117,227915250,518371190,652314760,994292195,677350704,685320032,814661836,72936207,945688577,488394089,612120421,169461167,149201916,390657397,812760337,25805324,390332480,180552131,789059193,604810769,710160667,114211412,783467465,550957212,62253148,616140951,50080964,104521549,213445085,617080683,855051192,233927579,505260990,702047172,415401827,28004612,861202814,198256831,888829907,237496955,655189927,761387646,795357693,222406988,758523668,147435383,85062640,279678625,25961435,783611362,840861035,199846268,530889518,941373800,87664251,781153757,395676081,391169955,580321410,613265041,139256007,631655209,119639684,75916807,315899612,892453794,798801167,228852472,872448532,460338229,693333040,965509774,990440045,30002515,374060242,628206352,432099783,998743704,967920026,757974129,487278240,676138530,364236224,641527688,46970451,625554119,871107318,944356631,775821539,577274699,294092191,943063420,4409267,327621763,158213365,198854402,537588079,299556144,301984256,60718397,753427598,996790036,71609550,38766900,867672124,73784901,217872518,305997197,921970653,413406354,562646096,485004114,841075218,420375632,339090211,4877049,170079388,88979807,173338263,999508493,331028310,769503414,722396057,439310225,494746647,899802175,762269823,572754805,379920054,661842826,908286026,416317396,378365301,227745605,66739468,696287886,903378738,460678848,185046133,669826063,376870443,702153479,443871318,980940522,283924263,246323883,605048619,526581572,504474278,723133491,306799296,523683166,717027620,507746015,619024024,722222778,291759973,862454788,515898877,923484669,792635370,865909701,552616257,256575166,196908342,835779790,930404591,710485380,695642444,971275334,760235194,769236579,434577655,542808935,629771404,321382280,673157547,71460307,228000531,210549802,804898137,155395790,787849505,505452997,44482531,853830224,533374172,982865261,880244299,757172868,896568210,325468958,954780777,693825159,411138982,580249494,342127857,820961637,773572562,885139938,15452726,415384169,92042140,64406757,205168774,285675399,811848937,15673847,757136075,40647217,8440285,259122401,120296072,26938334,874587923,109247787,928303884,979751904,517156878,732787678,424550689,368261574,134963109,636661306,463827588,777084547,382406833,436486883,702088096,221558456,733881112,572567700,561042069,7480881,576583452,980618522,57029003,582489279,518937306,623512757,991228338,665098303,372563058,12545462,810832365,346386340,699276715,736086436,53450036,789422282,34601668,48025557,879680248,297226807,334310276,353424042,799303127,762851239,849851636,729235006,446544329,290741872,618885906,78319849,616981795,668523148,994373745,172557265,96484801,967651905,94654551,842322910,866894739,672735022,477413476,307374919,601508498,873627393,106817099,174516212,635625301,200218794,914029104,177768618,585517908,293645870,787599744,970986628,216050400,503187804,539040671,626769177,615614102,596888569,607799361,510935445,282812909,198617918,471212799,209924357,284240355,51655301,811317340,878483607,442022664,368305205,242950615,380530673,828435042,979877293,153556787,700377774,324112700,533828132,333923780,6486017,824486391,419811475,257979165,62359123,751041067,954545144,71928924,593520876,412186947,277706941,931925908,865727375,452232094,987854307,421918914,365375273,943241058,387601599,768400593,107930866,189613456,361999159,942445204,908346232,128588369,604772560,746835349,329707869,295624037,434917636,719040707,400654669,764219804,82105295,44480105,844680634,82787154,942493105,703777868,868796541,198894638,670717338,459712020,514612222,286118275,973258210,482872719,760894190,22651272,314471137,31199568,295019440,464387763,997859827,280075830,372898917,304694998,28372279,85338712,359281515,518618187,439066772,440364174,548637019,865916304,898192883,950055490,633928954,588432881,826017206,377597782,514394566,759368488,327247639,727648585,697176212,999206519,26471226,425642228,226299539,533590082,755092367,974497871,942304579,389083565,56218963,119299834,695883040,12777916,987209982,333290083,770262265,180465350,695297799,924952182,99711600,11210076,535703388,162196039,43065992,425864583,347374060,896964876,600176826,470022637,341545887,425289686,474028133,795899324,47136675,86802140,217219778,862632309,630972343,714239234,323549330,753353695,665231646,71014372,596889680,435227312,545294324,834627762,552378301,498514106,163541222,796247387,715425668,392127993,996416531,225930129,53948180,626089185,524788765,394522543,795880979,434848934,253180582,918117605,466432367,938092848,521375041,577355512,923175878,905403957,964741737,152553013,460179661,160001813,314080647,262887587,967672198,670087217,616377882,936765161,205091973,26629480,749278701,323917864,486314484,860772605,172138631,92370122,578951676,752672682,624437188,87151133,344915905,671724357,627882367,667072618,957409502,734046316,276815831,782199338,486777916,801993155,862530950,332828783,118133573,577581643,765997623,569363316,74350885,769576234,14601775,16772925,240066058,986287593,852295652,557791307,323161552,762600736,798757706,625891808,761210846,594245801,295400837,739003966,833344511,371951961,70255289,962458252,891769061,652316422,890926510,210844254,962015266,786441174,387076671,26586059,584516982,765513341,839739201,588451044,770759860,607325780,767228026,403278850,115141312,282394907,43363610,812095261,317398598,162134266,973290998,481629702,675726819,514944678,281108117,897981394,485132987,328758873,218204956,774870575,576868522,236689186,968641905,163994018,496182083,804261782,807284016,577847197,557454807,281853144,539550718,542754094,435707883,533179974,166386687,927902027,783048117,593856351,374852656,785971972,852254871,637969309,554928199,688376923,260858139,355201144,496690466,631320408,553764083,219287646,141797028,162784742,842320034,612415392,326076013,911392387,560684495,354145009,799752575,538314090,180436263,511611614,587303020,653462826,205547395,738101852,996027374,78861781,231787675,122943913,274158440,849500299,181011771,449632266,397974348,224579151,104863315,328887524,90849041,187532344,960779876,241987649,803207345,43753226,605808848,151394058,295428416,630447882,192820099,513951592,346104255,943049732,22824278,598061431,931253463,521056695,709036870,38533423,535181166,801247169,512071800,524293053,576906900,912193665,432628155,229761575,153244751,636658558,516677317,75328999,884250092,901635074,646527300,645473681,800380047,498153240,27360212,182122713,918941161,537912568,938142497,408623921,336701631,144085039,665829181,525736336,753595247,108535297,855215487,146661101,593910792,156643155,703327853,150911325,334562555,944859105,385340718,421941593,178470830,996572671,243547182,379057426,595628304,965983646,852881961,446889868,697209448,398933651,977717964,55424190,887973086,166300226,757810466,973455254,874332112,879552025,886324692,897108836,674779579,296471708,788440697,312887772,997602573,240064585,153414310,974128595,33782015,895943240,9901551,568734083,182181497,911561295,17576979,805330377,768677257,900130483,985740249,242899961,457132681,427107319,802188410,191372061,717692963,654952736,507572845,690853586,873765562,954526721,408849327,148240527,3737777,340954844,678253506,330172032,107836737,807048417,828198116,945753703,468081396,859683095,858615935,553409093,959339882,680436495,969245625,679899159,774675296,742756040,148632439,125983486,961635229,872022717,110246862,738363434,239287267,56658625,796257520,478003181,986946131,397477726,562919326,67872588,391034403,928777117,58551267,28514856,868927980,321969177,905640392,515584427,960967869,798437867,899121828,977279779,997906724,767852974,12111555,488115938,148864864,374935867,730623442,221500034,393180106,146548815,493699780,312228501,206001689,31859736,503466676,985558627,525930166,607886313,113771751,509535992,169805988,300228197,448375442,359195237,438419014,724383031,636184939,585366434,199191449,994624385,273976161,550733406,998100658,75012882,828288366,396297292,616525934,85719958,155137671,855952006,873718743,266454058,585717018,275892827,237980715,621671141,161438030,583928513,235079195,737936749,766605016,829943999,101560402,129102459,268416918,907802642,758452257,255492931,740158407,444304158,697100066,771048846,585702166,964061972,496402570,601000095,350786984,864611653,193581571,473093231,913676123,822438393,965507861,924539378,309203807,206909929,498403913,687029904,334900752,807724158,566843211,46747440,782632388,135323845,442841556,676674344,410384017,467363165,294599796,97037228,767653963,833339572,288869083,324422841,712278071,503195240,160254355,660224336,291109730,631908830,71550555,679666622,991150769,819226098,212513106,354564316,108456575,373106893,667513294,303682132,974316516,807863982,861799726,408955045,77644592,651148666,823780644,52474382,106703788,598050673,993164974,167025639,809029696,670808358,429699464,197542149,73850502,534794958,338943441,295737372,639954936,388508042,317301933,952822443,905899556,467486722,939990354,206791203,73681600,283577191,555752009,111287500,576245387,514587249,848043286,986575727,770829112,169717806,171184576,327479914,512295903,26971197,321692150,823468517,391082224,340358400,382694436,486818030,881165768,906220274,133551062,327052742,669804279,209278082,570271247,373313316,439328505,620266630,793594220,578965043,290695151,307065819,949394640,177045682,602212826,96049494,328757174,210247838,422862257,719060153,954921658,24226103,773092338,953463149,968194564,290041165,982971366,845314942,279215830,495864033,451748156,827872987,340080151,184805345,610607754,535884825,299013656,269078728,677518421,179713935,989046727,18301660,57920683,731483724,900848214,52825904,696214300,401189475,824151027,105252073,603832192,593003112,762604209,406125539,984601187,33139561,653906283,999498703,447996505,582310320,855061343,46906558,22276361,321933977,764087871,749435702,142276337,128735209,326978717,249633571,543286627,289304347,978776525,87160147,353445877,378732570,801791936,894377080,621138480,924077546,190480035,256115125,364312386,811311918,681707947,211387535,281280468,628131283,952570763,130309544,201440610,831384993,880176580,993567292,22234999,972170946,189859980,153185024,166714494,664261877,35191827,665187240,654561652,243675097,968766401,31408975,769994671,487597210,314033248,887171078,241205099,622781292,534545435,336659136,622414886,373661144,923143837,551208046,667844838,905438546,824013148,748427250,488483193,587114979,310887714,640897813,893003243,601860024,195642160,890510691,305584360,54695279,567399543,971755249,753343949,234162011,409060960,530087451,501871699,86868806,651750568,297346920,992649985,416999681,383813938,540059771,518239015,590801937,992761071,894621529,440377782,558791608,623587964,304548625,243342273,639422665,898508597,436592197,642758691,271898036,119348319,253158224,660992444,536741570,695103778,156656767,896478995,351620837,799489482,101707620,251936478,865262047,100771514,687647351,255719551,243081326,675202918,868238244,806048128,354443174,345209722,499818135,412003709,275833799,780378306,642032345,131179207,994644456,434573881,572609366,109202696,247736549,45548499,168305540,25855552,539028644,838084178,195634569,877881999,795153630,612143199,99649234,953591950,910524734,348716781,264097680,663392284,434287461,803365939,952310829,267350773,326819885,966281692,899235678,900936163,914435349,88505520,952487755,688284218,451294511,236478278,131977114,246924892,142181807,264969720,551019971,988818511,426905166,834841473,525938130,262467072,472297577,385150458,805844143,141998040,392416025,373686670,731016144,986818070,576578277,61646346,162478427,555562850,921179370,113038038,734839064,730411212,101464902,902247796,289500490,164886038,361257526,271134648,443585811,978093540,989789707,932612831,970122644,627057654,486599714,261109191,557203830,474232492,301200640,99716000,436906676,616399995,683561555,537487248,436941180,199829354,285384162,762878534,924493896,498059468,123030675,695681815,963979975,510548758,285428715,165013805,203956418,49707070,760414197,615432650,306479414,960286486,985956335,728706938,456285815,219008386,423971553,832471345,58662485,984331881,857231094,513444371,481055286,966564175,470632816,645381497,441261384,806914105,795265526,962138168,418996722,41370507,52149007,517142171,529813428,78468022,230616086,829403483,884706201,291613170,262998406,607185705,752534067,594965353,274790343,44001581,990466320,544098895,558492878,471886576,943014147,554791708,1874979,781880722,280173212,99250399,756229936,177498028,414936368,412834623,475168518,725509397,523945421,761661322,256721942,154780319,529288725,230948775,318502761,512502253,537477494,717748747,198430987,304995688,330145207,427817873,763696881,785988347,522150373,606362416,416075134,644804717,352417152,641799984,621962595,876507237,695395326,725677071,179642486,216472619,311506652,824354528,910949027,251403452,1726315,486733062,221525975,947878183,402525610,535523433,821511745,443194141,581169925,564265124,977884300,880645739,741919837,684356159,749891534,33001678,978592597,267127149,253610184,568053779,776906682,721881439,841487769,975809642,925570481,441483697,189380721,366198041,161721356,410215100,992516947,593021218,240321926,537009937,203230994,3144260,642577586,713155008,760596040,912820341,254623424,128049922,326923856,968445748,457778365,21054877,535206496,466862825,270811712,824798781,941883690,444349507,707226260,772987589,793800264,886086834,640426477,50227608,564749465,305885558,727642831,289014595,614051573,407512076,739834940,14648849,99186616,660158856,285562996,825482382,621021736,62057540,276031156,276699082,790276406,260041680,627404661,734583971,717296828,967738786,159029564,739561436,332212576,870925092,468201976,169048396,817823493,485235858,403511062,631202849,296638678,157957139,375507838,665378861,420841333,778775817,114860752,79663969,227021519,446801892,513058339,666682184,636031460,395828854,913226029,623838928,453283950,19046958,151462489,200491897,827768431,956787051,883587741,854007569,382314275,249942594,20971012,99450860,455315193,399499123,471451867,905982506,228969185,182712068,896773349,363085705,180191290,703752015,418703660,57481196,592967462,49544848,401920591,64458558,464641887,103447015,433327439,513799205,40638869,79420069,602247730,317428122,364651337,340716629,898254876,309083419,519416644,682619715,49668738,374474901,927821086,11653562,269317881,343188111,924221783,763612063,328506143,89352966,334020119,407430640,78221119,97465350,383234621,202738216,645383190,699443847,298582735,247769056,119153600,568101338,749906164,263911750,13106417,515445178,507448406,274987627,596268910,92285168,903531807,964955196,835677851,301278985,856587904,521109050,580523956,406204449,581456396,248259332,278321283,418169702,477558903,768413099,440839322,546728986,210598254,419540972,590486807,722882013,873971570,204989094,463474400,70538689,63131683,308420162,514210025,167390661,184022736,196243219,284302438,657395862,808591450,454119793,471447118,555906393,5470735,191715979,881969042,736827567,498265505,169433688,482164997,605307043,987102158,247951227,406818851,862029641,412781650,956735258,674982731,437200999,332954413,464201480,186463115,859373754,845770708,447764351,535668723,498025980,771364940,631990955,784029017,261084270,788625087,985101801,198289699,48823163,688558680,724379237,328188856,959599205,312652758,653613872,980676845,232324029,671445435,618164938,546862593,577485420,289239838,271825811,766099283,661479668,697357674,58113855,523283423,783856062,390672199,902760716,961986225,400389377,202323631,159177623,760513351,457263194,912735866,114490523,231333697,817536431,540594920,424231660,69323838,931584770,794108971,449362813,277664537,323707825,280250869,454668490,726818961,856690701,200908181,599701471,937173533,9931662,93377474,378619768,1759551,117290550,987114674,677015739,96967429,865632585,408327811,588279592,144304775,883980126,187043067,368717521,541630887,666358916,670465720,906503714,894256811,991405442,70944718,997866464,348832272,471677101,951531004,755175327,303289655,426894306,45501738,26102094,135393525,162997770,490318755,11676303,759070527,540776010,454053520,520608260,918896240,117868866,972716778,969164195,191323225,379030176,388966280,437510300,53740030,796722033,581842935,274008750,161634552,638355274,26203180,483494353,916423495,856037872,847598723,718383109,931311368,601943183,359164888,839224728,843123059,792101875,133852038,790510211,267701766,981402042,898016591,500588016,876295571,342249150,596360378,138142632,899485920,130017178,581623972,882717011,801049252,538029056,539705018,392565153,80064098,690711698,755658132,126569857,600553860,361121174,741206612,957106762,265120433,587440913,826441806,147817907,782167071,672311077,867387187,221679950,45781691,880742455,686774897,620733133,123171266,701039743,253808526,455466303,873197579,414019911,489974224,702865489,361410642,79731784,980279437,8926379,772161223,322978171,13922971,845666184,568910070,638528591,925806397,395083788,762404960,432848773,326707426,965866484,19301613,949386881,628181142,247942160,501231058,12928037,493300132,42520866,148498185,163247435,142349671,762866498,412353933,453150469,853217253,264730342,214434690,268686747,143235947,872748283,225081457,982627268,240200625,747429279,840141455,912529169,627815034,141337214,794738336,32171638,223908137,772106131,254076562,93858575,721040272,859605612,183933807,217293431,830065037,163504995,75024987,826293315,639203739,811019315,678071310,453965886,887534739,127361844,312474674,907551426,58639737,63854949,941781517,503874842,701568881,302354862,368865116,966162047,368839881,576531774,281475550,258332895,693727144,707596193,479463,547331772,986088378,527635737,589169551,58680304,989457557,791821217,578664469,543713485,146860267,663264473,614305447,687115696,973597764,526897570,352232629,202466180,908013100,700233236,163258206,120305632,159639380,359368842,734462776,993451692,250862724,577661206,969705486,665486090,741180665,206054950,4229487,464511656,337331683,436458139,316007977,301328957,861747212,789396964,377465303,741473524,482311961,582989859,562796898,821711968,562629361,489702723,705571509,999596331,3079165,851341441,4438802,401800274,951405591,308874253,178997481,982950610,752347040,63195703,72126592,70364161,78410268,428871277,672739021,579862809,793892422,960816088,318184856,679659674,502505363,51222130,889282205,815819074,1812464,846845117,881733403,752903953,634463715,590775825,141277658,788869110,754568807,780877317,190930561,649209470,667346726,980138017,775442973,263552836,197536071,976771041,209834771,143692918,686078755,879572909,954713317,412941829,400807325,196617283,954919889,660108392,760570758,518874927,133750244,93215489,806696126,234120403,139502089,857452161,844076104,767756659,814349545,34606235,759738024,226023983,961254685,705621046,147800351,915721458,139860071,246602563,858354974,318472686,810801541,314218843,5194235,821263575,693238309,211810832,941649840,296531623,362431108,802163994,784635057,98407208,292633493,812222568,171440453,490909025,861701731,402922141,482843542,620435028,660954051,646960119,890563228,419433776,925107818,586199923,235473735,672874580,765391894,869612709,124836032,972351947,467700125,612457355,65071502,221546685,421701801,885278138,546530777,327338689,604984738,162526959,535020324,463012163,274413047,271077839,609891750,541563660,223154054,89094353,30827655,134704289,457934868,562835129,531041379,844205616,185261755,57096070,215924970,556873250,158357839,660896027,565388916,498134680,743409474,641333361,947253404,353561321,904926141,120973495,396468249,625887568,69747199,676219968,820193281,613769880,584991786,15614746,591093499,613526429,445011679,989246791,221779849,912959259,703114598,617744234,791063877,528524270,39852480,539684507,809630948,762789564,922162701,873037711,472989754,658592721,331637053,917015101,571630900,584086478,409181757,60272332,705506922,525591163,65741438,739653068,257460656,539308259,290380835,382044249,361157832,884943322,20054630,556102871,279491211,151761087,279386429,402101592,391851709,490512668,829888137,49967531,445961311,825388857,822508286,233659192,958970365,747869919,496561789,714401191,327628904,215894876,891802990,770297780,972337181,318471910,330943333,399645306,760502856,477105965,378770864,315753976,55280149,929361680,666404335,392631345,318249432,478303335,157933462,69692715,981855691,19864178,985852884,425080705,933440712,772474868,541063424,460064982,874794121,382684203,367807064,381808988,496167454,240890076,201333252,173752732,828458113,423288652,843115129,474316984,456335842,541599620,352508420,660551724,736363349,106396271,723159994,99894802,264298230,643236409,581592504,448332531,560854755,361777905,198337036,629708137,105259717,785921025,605691150,305027306,476204352,668391163,558178007,817385466,765330841,851572420,130481267,656224156,535894442,55930516,292686524,330983890,745465687,441331610,954857960,208010239,828975945,514835042,274660398,994905442,847472173,467254578,973904920,663054039,321747173,983264887,970016357,871291409,752523982,972265141,403776777,119607948,188021879,720697694,649955577,581731489,281302973,551456586,62219378,753309460,405348275,915350552,721011737,600817226,849931258,476323829,459708765,857508069,897756989,465382099,888159244,173175958,508403153,249648882,122286886,571368328,56386676,190909305,357641812,734992128,806897964,237293832,228789569,673990987,941582597,114446601,551553835,645522553,394207097,979374883,598715477,283733605,998123645,624951814,834439433,701930727,149303196,533186214,939423538,451966254,963516835,818662531,959147852,361020781,110439877,960398831,287800239,300981394,722179271,146870805,778717440,673230167,403808019,521637760,145938312,857557581,85955972,454959219,937129020,926182690,124090117,999678582,282963269,321695114,887821892,254570032,355965467,2366814,846618064,737923197,21188440,557281842,836945407,553729683,18925906,196357372,871926539,73199787,160152922,964642542,942737460,513101353,597752419,135893138,201032163,881399113,823152379,138807027,293702600,943620287,384252857,690307425,640808677,819454216,687695971,932095518,954869565,727990514,155399122,686200216,499649425,960830714,912660128,153131259,663880335,97948848,39636508,137246338,395177923,79450246,118807398,694282296,466160213,579181209,755245490,219498471,754890317,636275881,948680438,547074406,879877619,506253304,53819145,738145699,753776766,123006402,144626581,728083642,762375076,460283478,536021112,716283164,709884669,428129107,985109253,633076341,331652621,74915430,231962251,276353246,965091216,830269525,651455750,40969902,534073474,886984731,146720018,315308953,730577108,875025064,102439712,692454835,765032228,919248257,522771610,237102028,44375261,206499480,300345139,426849761,378126968,647093373,569682780,471730042,358541252,665173635,950640048,475495358,230893810,746928557,260924153,789107458,815763568,570142471,815321506,913016180,577090302,278874119,500821371,955493137,617080782,581235267,380961306,130042745,733407617,915179630,243225752,515736558,737427721,276285323,101323110,8563591,909234559,196978307,74700042,354923915,390247735,554865133,79696023,111412175,261338434,421593767,106451842,76429407,133260495,73079708,758781893,719466192,109309072,227356239,716978682,141685480,767795776,509083326,304636929,134670769,677891379,227335081,841697606,348124884,650034290,604095412,355790243,621548039,914670292,640153325,618568363,632196911,100714387,916867866,211542312,974663305,26174595,734664659,407895890,793929663,487640148,723296290,302605830,992334790,909279009,521573184,916520469,377739413,532525932,626914517,167109491,380710952,681469578,18999230,867594465,653805929,902508829,286874485,680294033,508371585,625586172,41796201,672033070,396033014,719582767,378720474,161026585,992207403,134948472,450565467,764106338,51496727,467009259,407064302,532281860,867518595,759128543,701169897,975704989,541366161,856678410,621208988,153817683,399574796,946631198,291566996,103277680,598657793,605674428,301951914,556169707,276403816,532576153,997752671,157280904,912278121,720624843,720002616,6014134,231707734,191288308,303224578,768197685,731052741,174267802,451108504,420635095,937284202,962900781,956277512,532427365,916571114,647440816,926565862,536766314,261809372,557899078,392951806,188514556,706179690,564465343,413950724,388904447,443878958,362656923,48623598,198557397,520531700,324259327,611388027,560831688,144339236,28588569,433175737,138122896,189110334,772791552,754567491,171321372,18711829,783587332,808650231,146691958,547412133,722901553,798606226,957573205,502461495,217356833,744028155,420927665,370476676,985444064,740220233,216218,50807761,919735810,290149999,409983253,503236390,46255500,953624580,328100760,595629327,640061425,586848004,695817286,281827635,90760393,138316057,246856196,434567143,136647477,250458341,357123098,209165042,795143388,706302914,862016523,604182726,839777447,16863091,958138387,112512415,627147534,978742156,959640147,818444957,631892201,933433406,23551912,484469433,597344513,556484626,681548563,356610786,4702757,843041335,724076823,735807569,997816616,326571580,637782160,565117074,860374754,735426633,529297544,425311659,430085125,453024856,349283987,180177055,725612697,208010365,466203661,809538949,605645656,483863835,465098527,521711482,586667864,858406609,333815112,762379244,168091423,456492626,52985816,201219200,854269531,901813517,485969840,55124401,626512861,276562581,806601032,900252648,203859271,217612564,652999052,3993235,457789931,226980384,883053984,498398431,256325258,64389358,655064202,286796334,215103714,596624684,976482372,349412806,902752039,772304264,39056371,105390464,623814606,640452656,137272451,968647797,775317252,617303692,872522273,296668923,431433921,161469756,166988805,750795822,520625118,107801666,50662398,233027195,307028516,647790567,705023526,268796117,627841412,856258617,28057928,672030291,835566493,437169008,725675213,457743818,868155325,564435301,499308739,222105546,542787100,360170228,121474213,627418288,923133870,942900783,147095578,941475183,210298634,197992146,487028787,278124110,1550450,159823915,583740613,455413759,433824941,312871994,786240645,289257720,381443135,771083647,358886687,249586927,99484981,825775063,548204709,291954330,347007084,719310910,851428233,359529651,960339084,979982111,764389938,840310512,555260092,295471989,426330855,855219173,661504794,453608980,401777563,850210687,824687245,414199912,622800056,315087969,320302803,862281756,446538455,136694088,161849178,929039574,531361966,330646043,511448518,456508071,304519673,920932053,172242913,740438990,429436408,193149449,736671548,207979884,363980757,539507624,803006467,899158899,422332580,736206632,346926774,927093775,207932551,104719478,994182180,789521215,972351849,90669553,449574478,171675644,739582887,753345491,505109227,309764401,802615415,356776673,77118984,462366743,619648207,602073819,552690391,301291278,23991898,420233093,200016709,362592493,248145044,659220339,659371117,32944159,909014879,4788290,403295794,31959283,850478343,101728125,299636636,237251783,650501223,838871819,645633615,533552924,218582673,777129581,951440650,841667840,627169239,712303694,791933706,243279516,511333914,818972754,313017257,949510461,61326954,55553746,703105759,651125244,980002860,157527162,75676029,737475439,769847289,248144581,976578782,967456293,994541634,944276529,710953218,350603056,567059966,524864935,231236714,687244650,202511824,542674464,173234999,163371282,505439323,25875387,999674252,722765128,717386877,351126867,397236281,242395908,348824851,57865317,680145555,195034960,469410315,808461963,234011614,706244745,904220677,654632636,482829580,609031007,640731760,793959240,459174292,880444313,444010661,459181693,205364824,200467081,911762310,726994745,537085493,221817999,362619890,679269253,234138138,550523064,926899014,554517506,222191679,657137617,252851507,241494094,43694345,429313687,672742751,497389218,68001820,933251117,578779100,536818767,868567937,993466873,822364109,939862914,531711785,241510833,102593411,431113035,980148314,440098619,213202722,411993133,240363452,867807747,211281291,393985044,802525067,485502959,469065925,379872775,613847578,59790990,918521597,643987605,281627367,140825993,407459752,191997073,638613757,930410109,969556005,461698608,715332684,858135384,214805904,124991614,166666856,401076770,771499176,377351047,20575121,355360504,820361256,885788901,31233376,212681458,828163548,513564113,163038701,221056767,127649653,609061522,331269543,693536288,93556479,469104259,50573101,818619081,370711187,535982512,423923628,762779505,310806241,799341376,946151067,3960223,783646035,857771212,843426255,704966002,782619457,275917967,61770533,751084851,230523737,564784662,353868528,123504128,153098052,410555763,360604438,35073557,471953549,301729493,635323976,42649977,821188592,662313845,681953711,57336454,379048760,452296545,314648162,303449386,539555062,404794748,627777500,29510082,798341596,683809682,101743525,65714924,68427157,490845782,952563337,926128403,876986962,802194567,337315521,15802358,58141432,387813728,208283963,39393028,956922424,992910398,886615923,909345821,464049162,866985351,678786397,128336205,881657557,761891361,277169709,337997004,232461506,318904378,556244436,285946599,855681301,638277607,884496565,42816127,313435786,213739443,841007863,476829028,395214147,807608775,958440693,908924073,369357858,818383695,535862567,714893575,418403650,282679852,202389908,696754006,8221558,859632237,116714456,521621964,472803821,135872646,931602767,933668946,909441594,490039292,385084722,857150847,204495481,323899113,984896423,628513860,673288500,155970938,785897902,118680208,941528213,276948865,630476122,499472033,52260048,338669894,962286552,323279931,744119327,926564500,940815793,797392149,391316729,441702709,25565988,951725490,495607255,136997644,648047316,486488103,42638659,577708979,571351281,988136038,864306615,449503632,755245174,261520402,878172560,919028647,10166481,502289385,41594275,554647179,86595520,701057722,516649626,273878906,346534755,880495465,150735494,318877910,107312611,562406881,453159847,764914283,36464457,251079923,450930537,194886681,469732245,291754851,437599595,339543117,430859937,53168292,809111554,408678297,272766984,614000088,307992935,568652761,327400157,295636277,934310965,780993741,367170236,907321815,949575225,947887253,220984371,149122629,512853720,407730457,278413736,993592174,752134747,765215404,877495586,669171736,926288086,741051721,539781365,862166883,855580542,582444375,964995545,117385330,296824061,658641889,642870898,720997733,124321281,60582246,344154942,865078438,315491644,555533789,473718087,992194488,242412654,374612234,144458917,854631890,57224347,828651771,248452432,166997303,310070696,535163309,52648875,454611931,600407619,560632253,88886393,391815597,757928737,821424655,103258391,467992923,388061415,515743327,514200510,891437161,636736025,46333228,333143677,897521842,925226900,508236570,202671502,673826584,279663080,536377451,734923940,647474757,85836296,638042053,401379187,252536216,102101558,100525737,393650171,333432731,889576646,62401101,338791562,399310088,849876097,396339105,548214215,383882038,312360332,27455920,595222641,571214428,478966994,784763655,349235752,572519924,873547300,498181499,150440555,680679126,141889012,278991695,336553248,8921143,548786576,603722012,136040038,663273023,564021171,697426386,227788138,565134272,628788780,905290309,24653131,77776532,860220787,257712754,811267518,804177543,376488333,424320224,68496688,131624993,171658817,123244108,845785283,78988941,977372139,857269702,871747361,254386459,272605186,451269695,906941088,508224802,894480398,363207739,763562666,455896686,201859013,506188689,744989425,47140295,162162439,808200272,996493791,475401267,988145868,659810047,436620502,143977729,121474848,713606609,327086158,802296303,621437672,430749644,656096744,809767044,822576278,97453744,732444817,340438095,816924068,825656062,160379491,98469055,527163371,270293024,726550349,464533267,445611548,916646716,23063085,435192476,64312306,195201305,110820841,208346466,216309310,945020454,203803254,683548248,114465912,794296974,584549643,384326627,606691851,831477122,756274208,860689028,935843389,283599291,4468527,98970744,980634965,800989273,779411176,992317662,54423089,995557470,947722306,97706211,667514671,706038610,335950484,984229651,861492590,593930018,456167902,217193869,552475929,305185825,527506940,877452491,109820754,183732798,772925528,531355484,220065349,398456216,318907861,337618458,491821211,734557005,935668222,698774147,155393870,931719756,706082167,316140346,335061582,35477916,267551062,314005453,816720238,861158967,856690177,871790531,280529427,104546883,962577162,333344464,532502637,483053306,326101898,899270546,402521898,652288563,651075342,738447796,314833150,756092358,783238257,328212670,606673609,416503086,798848873,370753928,525824015,376340569,286512060,544393933,715782211,824457051,516440111,497838941,345023600,408401969,198363043,737777357,343849677,390202932,486119556,935447843,648429277,807035696,553335004,695026529,243518613,515118936,405841241,63289368,418654178,531013089,374106017,444100349,713839039,921611338,121475398,945571623,84917067,649271968,822788193,769968203,2003389,921003059,115255953,325386387,584257454,897376546,449943987,242160958,572803850,610570553,76568431,475417674,303378948,195695174,626628564,765751259,592735973,960962996,568201100,769644904,379558529,903539876,219531127,714780845,36560161,601742318,388784193,697086188,341313646,603060539,457219935,175168117,389922353,355068731,721928824,731710534,226079808,260281771,893758701,300440159,655378819,135723411,118200461,245211671,812006880,103700504,942234694,144324307,894394465,780471434,510996774,72478729,856478694,787225277,632998213,931684741,775846026,464866876,277558419,447634995,300802845,444070482,250251481,385167839,799265561,296736530,236276298,296184287,681266398,774966424,446862489,313863083,850830395,901084720,394846521,227212786,331095015,383202984,321857121,281396737,199021857,935944621,459490740,54124459,667218245,863513153,710517655,821719992,283061705,421129389,24435981,431160939,610819015,383207716,670543177,7924799,739594478,385168401,778638281,532246924,17711174,356584858,259597695,295308915,737279727,48995912,917207202,938527187,639165620,817980572,774027366,743687087,787293211,963005908,472102133,750538057,985936856,227018196,641053052,285728937,173114620,400615894,85384032,85227924,68245624,652766134,415418537,204154272,280674683,280645444,360681206,715152361,313300322,147240609,455890354,670654287,243568972,583096254,549498415,747648607,192779843,744349883,999510253,515333874,566884111,662356214,288585467,671158688,525577531,554816900,242310621,278340004,15246909,437216395,727977693,630621522,661737011,647015315,624957561,61404841,876904306,705748118,476749041,7018015,944989156,721809888,377127553,416382070,882523922,219352,32885946,626589220,165898100,470087070,454959865,191255220,452071528,795405980,297099466,509515136,137929847,996591702,986076909,751599388,583776608,512022388,61494529,212815493,651236864,268725883,52923012,114907428,249016736,609688655,936962582,33869102,307792084,780921619,260031696,160227467,826554870,494628516,868020196,944108991,883580920,999724389,390282350,402384077,952029230,815998221,53406663,593814771,508177353,814406192,198381054,66141821,514498158,724138819,542722675,220649257,640416825,390279363,683204820,976738941,853373983,160393652,584450745,685980995,796164916,438865151,359092965,514367656,704893459,650366263,261642929,606408666,826613759,334281366,710827558,826403833,966287082,136606230,184149948,881647365,876014900,570779698,733309949,658259318,734943571,785677179,988209049,426824364,557027647,197565271,198704881,155528137,568836093,507743074,540580129,60006153,778009040,584219977,197501868,935429837,375020479,189839921,921792891,283144435,879866899,894227205,545051823,40663883,867995130,671716270,158386782,883485152,354718481,805254076,962781156,724447917,880066679,250905297,336628214,782842037,533475253,249900953,359278584,194217360,688305393,230966441,493714485,206438084,793156367,50144823,856317106,875893636,659533988,157609166,866490097,876057372,896080205,329853220,257924897,108528824,206869848,832595396,876722138,450353417,678170658,303643652,871445536,394698402,455301108,215787185,503767320,38297135,270933695,225243752,797892918,716820157,564640099,905707176,289414803,238702753,82987182,208803660,834390903,329840506,24401788,164590165,224328525,476272278,452782631,2477739,523688891,856270562,373101239,338910356,756858895,926878457,909065435,843645467,910738052,764691729,458789182,778310417,716607225,435358894,507426690,907630372,39253513,313475971,978012191,762975753,227068085,851781227,485084253,390749589,784798572,425787057,474698486,730783945,14797806,661800859,409986096,192991055,746657298,194818146,673996452,681699084,771265856,534343068,795665326,695756403,260146133,299241857,295477938,522924613,942252546,170388700,639540572,867094859,224854191,615695478,930456982,27453024,240348152,95587826,672628907,216584178,898898324,297439899,459790635,244377046,817376306,163033038,701817085,727446814,413803075,140706721,339238546,663885445,765075279,255347580,750529195,521119218,956194005,138520675,10997571,535793717,128237885,901199024,570937087,362268595,87068178,706372103,394706707,132116953,207016075,724639906,223407117,471004794,399873566,349312579,552734465,742588157,834475897,651075800,197835140,15810038,649799957,656427359,109592150,512464383,611030716,622186096,108094138,201732810,995636599,631931045,273549032,628485,139288109,231960592,147258909,562050831,309860348,115696196,775671666,948240946,711576367,383280721,652592487,173532814,148131679,83417500,538675245,134184794,639309342,963716660,32689876,78179317,478929968,276885609,855168310,83321509,38695393,366484220,801947362,369939160,239838131,23436117,453119923,361419918,820427067,873486125,741568723,116289234,68564941,265686422,724529031,976148398,676762508,470931524,263822592,634885707,61358670,933841990,835553148,764513143,404313327,613717803,635066834,231186638,755124546,647314589,715028866,18680045,933593688,536637923,830446031,996802574,24700890,684273653,672311283,189767711,786822223,777794579,444904019,867755651,713078963,786037061,825396472,971145665,517690447,664620879,107054067,129383127,352705374,450335159,56887110,492936967,415060912,887577513,768276393,759339500,953936486,611757399,207092003,712875467,889040476,963510056,584462257,851633997,43671350,744609268,748036021,357161198,346731964,552080445,891045515,305212304,711010915,530088156,15298566,867273549,777034667,907864602,470501800,373392662,851871264,892772002,469182940,169291253,935389580,337007423,625502603,988080053,406465305,913566925,964383368,57754919,529403053,729588455,50754230,578351544,951622654,638877682,450956728,214371734,321365342,853238829,278529367,972744361,403282816,344401121,612834374,633946061,856311577,443039185,170048188,202990088,101089662,560092017,809740896,477052847,969915628,485879164,788086254,117167587,122741210,150726047,763347987,648775962,423664370,891979414,494135438,66081679,365619016,963535765,839528910,666497995,884747931,321318971,828118574,19790820,370340154,254941322,776474759,729174917,619466139,68812157,810886561,257089797,532234002,677431466,966405138,944686544,269153302,65229260,761835753,286857082,571969653,673711021,668117941,167136444,527881679,705354502,156826022,587025205,912087863,619574896,601875852,936422047,690011813,935066231,439673006,362549370,389478681,599422850,169030089,6416230,404219024,737920947,563049884,961630548,318982969,53126913,60973738,7844217,937541366,853626769,459220143,378708547,262053515,953960441,665331,828222134,155280703,947811880,43603399,868551100,15920514,608812227,349276701,252376538,881308241,312995590,610176361,566273805,777903789,262913571,287220297,224504911,734287502,62131309,843587788,440340192,879100404,948645570,102294992,318964669,9843167,293685152,231816491,142772666,455128796,5103661,158122946,643928225,793772847,764843511,257621809,873823880,417842331,320093097,275756920,924633328,291843714,842608318,39538519,615678187,120965324,316701470,221452920,222216116,914873417,230489912,593551894,336638089,802754784,230847130,648201684,513748658,565234777,539469503,697354715,383180872,44826254,34562572,300244659,745516320,427838016,28440583,860658269,980412792,166243971,718007423,733979051,399979824,942067520,754719426,269944922,681165536,564676153,909443226,646194780,171933270,948776063,198227120,259740318,351229649,451471299,727529115,664319533,522289217,343466944,90489726,148866932,294194513,91861612,66153522,891225677,947734957,213662582,588554948,167725584,795374177,49408635,303560075,566815094,120611677,686089283,156897881,144703893,771522361,207191063,926762001,367095391,248486092,15716383,711001488,31461391,72593824,910793729,747892789,388476691,208468709,303863592,511144000,80830207,822458480,108852580,918485505,327394407,261841178,909979205,967219559,913407173,955358645,101054603,907311491,168326932,568752691,810671110,603898429,965649950,76964110,575779225,407857431,776180111,678277182,390466324,399624461,167099185,240317062,160071418,44953428,33299734,625964317,877100756,203714184,890057534,462715883,130717045,483827505,722983461,62593361,83745797,295878577,20855020,17117369,838930547,570511689,767455348,145612332,135728942,388088117,498181748,205662483,539275556,166313055,588679619,340748357,809874548,782190613,236381251,122710356,272457806,95049701,467482962,537755348,411576475,264506711,674617650,571283757,659119862,980255541,7339986,253087596,111517630,389575728,287516844,680594998,661288147,213073176,238024375,718484673,531498661,611158383,544869752,578044266,896279331,500796425,49937933,755973076,736007603,608296257,755591672,509343673,629628313,143942405,738647456,462259072,984920586,338495769,183126490,884204754,665358849,365709988,312100405,991261133,56847355,391131613,100383433,405043909,497294671,815459982,544957390,224521192,76827124,238625321,721673053,814914816,543814858,636740769,190942068,195636868,113420346,338706050,694562406,819166544,144174314,205152809,98834916,48588664,956881994,759903659,586195816,839372111,859838092,746689247,686267542,90195685,900253990,833092256,2208926,782975137,632289558,919363153,83931581,671726322,384868664,723134788,308383613,709499298,328124686,31805553,246341746,709766671,870996758,154243894,174920564,247503165,474470058,333061435,959952795,409793960,647008892,189869209,525264349,323512258,968591330,670727490,296202602,645170082,362453308,76811996,534327948,318285892,528351397,612694926,878699607,30899982,678290013,495511749,691946518,907067505,324002672,828584036,683795315,984824321,606990196,590670816,894033957,888979442,848843945,184445121,433658251,759343247,718783998,841334890,237148301,273087922,819034835,114042946,172321533,63780727,200899363,506771596,19144357,594460650,326979803,17920114,391910102,708363860,221300877,85571428,28421010,248959945,566580884,832514478,102595125,962962514,803859640,455652059,929434446,976546422,839461377,718551065,215599943,715440509,481196138,602881300,382576817,144548146,989308838,285999966,872934987,476246312,109072012,681448571,121785927,255807472,367817513,421413706,467321384,839976554,804553637,841160275,892184223,978467871,37119606,394476047,702813164,206722500,181313101,596379820,928769420,508968260,773871107,504312344,366386878,49909774,482287536,649284385,618684754,323483473,174018239,303073054,674773847,825237767,256244806,244828238,653222275,61878265,842903064,4827435,156907945,27394495,589353832,349590765,293388716,405340492,1523045,527113567,787450589,994190974,353963446,868399696,608269787,564253943,605997245,107012830,641477549,238217673,68344761,21747771,397420231,40313935,277216417,27936671,186499826,288200858,173841458,15053501,983040204,348401901,903593336,80701485,646278467,268614579,450591353,631192733,474912401,320094218,621987324,492076304,579064275,115390891,868707062,111820103,201901004,792762286,803588492,947621235,567102008,717928789,238422916,944186723,517443820,640946485,327796333,5947130,778381366,317334335,977580785,7216268,61826611,244832426,413608004,320366122,48983675,957097736,918335957,972467975,375346721,719676321,101609529,567250848,201610152,664265361,948974389,263704014,819937462,895799543,528453468,627722093,721543213,617491914,73818255,191992096,5394129,71851697,606287334,78946980,823178865,846116899,74761631,448577638,543780388,868876265,214354657,234875175,329470305,215997412,867336158,344318155,173212484,907228814,222471560,463169812,536773046,182010095,301533798,891173521,404729324,340534877,995953986,659507417,454161690,514253981,727389577,640821208,207403134,596812306,855153701,452005434,808245080,551310248,754194902,82315073,474466306,4351296,553950790,675700079,814086787,431332608,97151404,884377883,612466767,49706787,462714630,775800457,116079504,270793104,624505864,680812576,68911984,897102808,55940292,808838338,736166770,871745601,409053509,955888760,32783796,385493505,918923190,808879854,328915643,678006707,422957627,180836764,649922575,904023998,144896689,748788154,402480633,860193055,817476903,857472980,918195773,11661818,825100747,264869093,821264381,112465168,337439341,831178938,175077593,465608027,884657478,604520870,564323892,282878249,85344912,484075639,412066384,930244050,459532367,971332326,470327231,269290163,290819392,683848398,587842181,152773888,473160179,792899261,552609804,715261511,850194823,322962459,153917127,405379514,827758937,733975911,375251717,976102183,399589056,715590437,467328718,620499574,678441527,891905274,870169328,606400159,880466258,971499534,267527915,180412406,91241253,869081640,365677112,694955905,254252234,544688613,613288931,458303761,912144114,737014721,24984219,96301630,365365740,968393770,82508742,863869456,220881790,269072995,396235524,563875876,984158182,693408168,188273659,435536751,796400187,196326986,768535618,600935836,221739561,163620712,124856659,682709232,428296048,433288595,4696166,621079679,581265092,170188860,328820681,58550067,306909274,990864338,738064867,826636119,436992625,219004776,17510559,546230523,278208402,618203663,125715971,765853400,605346629,235550750,161245353,177674236,577594584,385754453,592206056,313965382,306238690,346481172,44262819,112440354,812747272,836488772,814659738,543068199,161289534,518776007,956941440,718717846,709132222,897301577,903616970,636093227,665395679,140808415,279188159,403869942,990679704,899683399,335820172,849968952,286759202,990940962,663019110,641007382,662340694,146969951,931008501,623088697,858981998,476862387,984006549,934948627,394332214,608535321,145496236,542591698,836039360,330054288,830143272,865743561,365626973,479209179,763013388,663114148,523864006,583246098,193092800,534381095,387020007,385585471,627626185,602057495,251365373,831217210,156631877,373906014,475434732,1284572,955630780,841781201,232917984,701522951,971605689,322567576,363009331,442816590,272647350,431340372,871442262,669628592,223364998,131965207,295271545,37740501,874359701,344396386,546319980,813182392,331034626,536394404,898790515,782249753,299714570,546161963,45696715,575677511,22497353,495488313,996006986,376360664,914324173,567592220,52722418,321082017,34423124,91010292,402497731,449648018,165090130,326146018,417129788,522704169,214706361,688188250,993716076,398595974,121283594,295201836,369683340,994791779,474674579,149806763,893735413,117554216,988882713,523811561,299725144,407400403,658891229,332128765,505373023,426053452,816976404,824792934,295172833,896144731,905884000,39074135,313116086,988280987,907873913,632064278,81001008,389680784,344940600,486108479,176667664,357891284,196731469,777885385,443068422,187791590,354712764,17329945,657360912,202236358,109312486,376178069,257986105,419969255,616494876,2200030,679940641,814245380,709867795,541622408,913296531,406320996,127164552,670003496,134014275,514620935,533869984,774434776,628951078,449754115,155412096,842824651,356999719,586059305,307107118,634443914,234934551,979068267,987072769,666494339,576762394,208934512,918371116,639143492,810772656,426552063,734780669,769446830,462635037,409731739,526626302,47523207,925514007,480233457,350060901,647752558,991202260,872601274,291434712,280171914,487310326,360835481,288891402,384617111,730566148,947360109,608284766,896247050,678330134,682060112,826984336,732205146,775266484,556926163,954103099,790012901,291650342,522704788,958640496,614398995,517798200,649370204,535207988,958702491,9034256,137480512,745224070,704505292,285075641,962253249,995412662,265535405,822632670,153103976,799767834,144549755,871482780,374948815,33630750,999072134,304453026,165175011,881143724,656196166,511651598,30114571,428854811,530952497,983444680,669453474,217848176,854647545,819621293,257304790,764904106,139680396,453642727,224191675,484820870,19968050,212908460,690923202,388072575,916197482,615249609,645088562,446903093,529518975,160528086,282408005,416563365,159693567,646868850,117649378,871769655,653667218,750685913,679853807,721779915,804963832,575579790,662032102,992886598,178326580,438527776,45953666,509211648,59116543,661634323,994026837,169223039,400727903,295987380,513378726,531998765,648273318,945821807,49979970,141185675,536386772,580133882,216389810,909740808,708373584,579089343,440716101,939150444,73018223,816004753,673552381,495354988,889594858,175105531,4578225,183492206,29821252,492967346,297430043,905816400,273521377,643532649,976778360,709931468,195923852,347532759,894758365,101266257,735439303,936543254,969609029,473739052,449073983,8449383,747126826,518186656,474045794,645433478,564369444,996448809,445988377,559579875,534661543,885054730,616573609,614406086,917848130,660836479,194004411,258565931,404990522,720112985,753472195,511761945,226994280,140042872,966394922,213382457,943371412,930472473,50272282,815452004,222224032,867540344,864359354,916273491,601327799,656205167,814597857,76668648,149916170,745937038,937281048,493785366,361719464,505553104,707163921,160475219,930242717,100545594,417489200,122770958,940795821,351631704,757319262,823463853,309970852,825026854,902220271,35634343,614544624,710282598,329798540,245621199,878109441,973129768,512792377,456947955,646725920,250884278,537493399,335263295,401051703,227246116,142023866,371714455,136930636,382450575,999265458,428346323,496926296,407112895,880379338,638332787,638851539,491165185,444132029,571960105,860791988,148156007,196179334,619602175,419108790,86562390,503263225,259646099,17814567,876681909,356952483,804371796,790561128,874542708,321143369,782313402,735228253,890987865,302338828,605874242,954934573,8860431,3293796,713811171,589375029,438621656,667248271,92226958,147083510,998469480,754929270,306386770,139681531,379770849,843358817,163961453,818621457,969619026,61374382,222548801,10051667,498157229,312401874,32573822,334424106,30836761,748706430,790725568,100221342,239965731,580089687,168904357,572208108,69819253,448591143,405615217,793421299,591058461,108598144,515768685,27360591,602493467,736050609,997503903,323715607,540974564,306882976,568689762,561447651,748617478,228889806,389459605,887051918,769231407,468728310,100936879,312044337,889322493,15947735,159488069,13542712,392762516,538346648,989743090,130653799,448813720,133616635,106915556,453758134,745621851,963929726,455565439,889891610,316705741,873916259,956023796,548191423,685633560,197721406,971512224,342398484,474613054,637671612,424098657,958293390,275436776,5350793,270993283,151074874,657113274,249855422,22445792,438574557,613101001,496482413,271015540,619699687,148754160,149010325,659913172,837281495,226365993,745182761,768191015,24566049,740462938,100896564,360005059,49833673,716743047,253900664,830773013,101949730,943708059,696630435,907853902,565599364,75041610,248515305,881147903,725637350,872133342,119830742,314949199,890351392,275877248,987968806,562961727,38016487,344352172,882588158,921337044,535203555,311530458,880415200,379345874,376730547,284607060,343941204,520767034,595170896,36939490,569164272,681966044,248835510,679134142,206811155,266946804,537645190,140880555,877027263,555538736,153058066,308134450,381175890,790242306,510593017,18880281,217742796,990941514,121889899,178006509,971403321,344873438,537522084,978403489,562345710,879011481,808652851,947062486,433862494,679574789,435252022,457931136,409581919,71419470,435958585,207915809,492031004,51299637,74743669,64909429,514140707,977617285,809400696,415823184,180800034,631991358,778304468,338397753,691848568,969187243,813760135,977744229,946042700,289803549,361882032,202374679,443025607,443267483,200074251,693162475,502910904,816186204,85036355,572354415,21806196,209348017,611171316,291633231,314122386,844021211,550822719,43856719,916756946,923850877,444106002,241222497,509575212,743535845,227043643,228413976,515159702,820392980,777379741,245637369,454618213,102660625,123511757,125844577,771808135,716607370,677593324,846388350,626780922,432089528,674820640,814096278,429468609,763152109,154021770,455104502,152076460,320246829,650824671,918850840,995827849,916566522,849865311,700924621,503415528,650533979,195178326,847405314,424488086,285492303,828385776,698566494,899433343,203234243,412057948,415909139,768821622,434339268,396038003,732977015,125013473,809346344,587423394,264102525,914694150,325140336,355726266,433615430,732045211,6359416,519840109,776739771,105397903,564649507,205518923,242765560,584653136,460818416,76861767,373267740,390048141,54157605,135548694,269081039,374220051,43143250,127346402,12419532,107536534,402315852,707768302,338442005,566299067,77455537,469023376,70272693,789798795,555512534,672655297,108561107,202241319,78070537,775621236,991832212,132384445,16711717,705584356,347821782,86853698,308676576,216189347,187427445,312962726,466148894,524832025,696642381,660136106,517305912,187858644,367213178,201537948,269032583,985878271,386984896,675885593,425398486,217233196,562299619,307906147,168446775,385200018,650417602,640648512,930885849,666682510,393415469,875060288,112792746,113244861,664968586,652923941,259434465,382989955,513253093,906322942,84169955,374858,353122393,172208508,645752088,583696044,897881295,946405860,609378072,111943114,942772839,429545109,626111463,439261660,596038069,116720626,192273427,812143396,34641204,100835364,347322264,990452086,413774019,555462675,71409980,362542669,138758965,110092053,646253509,546480949,82667899,660927363,433238152,138088806,631306236,364702285,793841502,253017078,226055777,477786696,654610738,256091396,657793081,252331750,679161369,959879800,67751854,544783858,729563046,299804678,245014337,617532677,512721415,401480840,43378884,575496819,120791666,429405158,231776855,101719898,149863618,68659769,659555287,855329022,507469039,393019110,257634675,430912810,802687211,987480966,960225594,194356063,906277575,600852351,223373356,990305889,632424175,361630560,597595330,9625856,844683867,8102382,899853916,364209458,164742251,55943524,300075905,547300730,663715445,952373409,784871426,419379584,117069871,189652167,647247078,808739284,160309102,495170330,126736101,109662553,683184345,21097077,445955686,173125966,814178118,66107269,577294494,971677393,229972451,664644821,704690460,842319001,811304159,43613795,605904087,271966106,42118165,433800197,351635148,454325703,37212243,877192634,666127770,858278552,322529243,203421772,894245170,442966140,27707533,987362441,254441936,710902095,802312540,660543880,426690073,559836554,259123841,385104002,914386970,416752480,279729431,283654112,982738703,578856348,533779972,794833550,13855094,201695534,8487126,775528725,539292033,148683190,259697960,628602439,719200029,420586614,747894608,37389869,14543772,946159079,669654160,827543869,253143485,160276325,120416396,490918918,208173741,95234548,563183032,136757783,902881510,330614507,685722113,375247851,457627219,56157321,316117596,527937585,756972293,234750472,371808638,623968726,577418100,798885739,779732144,85946801,483766550,431969402,85839685,438494296,312716551,301096803,927557534,714615976,107585732,270383424,533642659,29748512,416315161,290659023,764519017,197275761,410693504,76083229,550166655,922237103,299732787,295201382,311712793,834987068,130807855,488882618,47767175,11439974,1461861,506330986,433424091,857477867,323740012,871378873,267633099,890148887,337650380,343336089,422253605,179434849,728037538,610463957,429144823,739132013,427163548,567428404,449009926,873222005,665377839,608963133,154519865,283947431,124737112,634853075,214524578,517828205,966380997,487599102,110185953,175957743,650677533,45728976,984649502,957126365,886202605,24563249,569607822,985583707,255028661,582478972,412508472,501619392,351997917,934200924,563380168,571011714,277880433,891639667,873875023,177075154,9848648,396335641,98374400,921360898,338307852,892261139,745392752,561625363,672760530,989512167,797188200,520955816,428223438,191998531,573109071,832777219,357662174,327417757,396022190,196683636,372758566,233172502,722741071,31239710,989076494,80516691,773325903,13237191,413459323,814544984,190685327,560710110,584334039,464620285,18109922,473127574,292037399,800849997,167942598,122399382,865555904,515399606,760592100,50393159,973880138,89142516,269242009,192391540,669175178,106909682,348438842,236429924,401970368,446940596]))
    # "gdhbjaph"
    # [74, 34, 65, 30, 43, 91, 14, 10]


if __name__ == '__main__':
    main()
